跳至主要內容

1.2 复杂度分析


1.2 复杂度分析

想要学习数据结构与算法,首先要掌握一个最重要的概念——复杂度分析,它可以帮我们分析如何更省、更快地存储和处理数据。

时间复杂度

算法的 时间复杂度(time complexity) 是一个函数,它定性描述该算法的运行时间。用于评估执行程序所消耗的时间,可以估算出程序对处理器的使用程度。

时间复杂度常用大 O 符号表述,使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。

相同大小的不同输入值仍可能造成算法的执行时间不同,因此我们通常使用算法的最坏情况复杂度,记为 T(n) ,定义为任何大小的输入 n 所需的最大执行时间。

以下是一些最常用的 大 O 标记法 列表以及它们与不同大小输入数据的性能比较。

大 O 标记法计算 10 个元素计算 100 个元素计算 1000 个元素
O(1)111
O(log N)369
O(N)101001000
O(N log N)306009000
O(N^2)100100001000000
O(2^N)10241.26e+291.07e+301
O(N!)36288009.3e+1574.02e+2567

数据结构操作的复杂性

数据结构连接查找插入删除备注
数组1nnn
nn11
队列nn11
链表nn11
哈希表-nnn在完全哈希函数情况下,复杂度是 O(1)
二分查找树nnnn在平衡树情况下,复杂度是 O(log(n))
B 树log(n)log(n)log(n)log(n)
红黑树log(n)log(n)log(n)log(n)
AVL 树log(n)log(n)log(n)log(n)
布隆过滤器-11-存在一定概率的判断错误(误判成存在)

数组排序算法的复杂性

排序算法平均时间复杂度最好情况最坏情况空间复杂度排序方式稳定性
冒泡排序O(n^2)O(n)O(n^2)O(1)in-place稳定
选择排序O(n^2)O(n^2)O(n^2)O(1)in-place不稳定
插入排序O(n^2)O(n)O(n^2)O(1)in-place稳定
希尔排序O(nlogn)O(nlog^2n)O(nlog^2n)O(1)in-place不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)out-place稳定
快速排序O(nlogn)O(nlogn)O(n^2)O(logn)in-place不稳定
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)in-place不稳定
桶排序O(n+k)O(n+k)O(n^2)O(n+k)out-place稳定
计数排序O(n+k)O(n+k)O(n+k)O(k)out-place稳定
基数排序O(n*k)O(n*k)O(n*k)O(n+k)out-place稳定

分析复杂度的一些规则

  • 多个时间复杂度相加,如果都是与 n 相关,则取取复杂度高的那一个,例如:O(nlogn + n) = O(nlogn),O(nlogn + n^2) = O(n^2)
  • 多个时间复杂度相加,如果其中有些项的复杂度和 n 不相关则不能忽略任何项,例如:O(AlogA + B),O(AlogA + B^2)
  • 两个循环依次执行,则取复杂度高的那个,嵌套多个循环则需要累乘复杂度。

一个时间复杂度分析的例子:

有一个字符串数组,将数组中的每个字符串按照字母排序,然后在将整个字符串数组按照字典顺序排序。求整个操作的时间复杂度。

  • 我们来分析一下,假设最长字符串的长度是 s,数组中有 n 个字符串。

  • 对每个字符串排序 O(slogs),将数组中的每个字符串按照字母排序O(n * slogs)

  • 将整个字符串数组按字典排序 O(s * nlogn)

  • 所以最后的时间复杂度是O(n * slogs) + O(s * nlogn) = O(nslogs + nslogn) = O(ns * (logs+logn))

时间复杂度优化

  • 采用更好的算法:举例:1+2+3...n1~n 求和,直接循环法,for i->n: sum+=i ,我们也可以用求和公式: n(n+1)/2;有些问题可以用二分查找等。
  • 空间换时间,比如用 set 或 map 加快查找的速度,用二叉搜索树或者字典树加快字符串的搜索。

空间复杂度

空间复杂度(Space Complexity) 指的是算法在运行过程中所占存储空间的大小,依然使用大 O 来表示。用于评估执行程序所占用的内存空间,可以估算出程序对计算机内存的使用程度。

常见的空间复杂度

  • 一维数组空间,如果存储了 n 个元素,空间复杂度O(n)
  • 二维数组空间,总共有 n 个数组,每个数组存储了 n 个元素,空间复杂度O(n^2)
  • 常数空间复杂度O(1)