大O表示法扩展阅读

Taken by iCola

一、时间复杂度计算

---

如何计算给定代码或者操作的时间复杂度呢？

计算时间复杂度最基本的原则便是，只关注执行次数最多的代码段或者操作。比如下面这个加和计算：

a = 1
b = 2
sum = 0
for i = 1 to n 
  sum += i
return sum

其中循环字段执行n次，时间复杂度即为O(n)。

再比如下面这个，在两个等长数组中，查找是否有相等的元素：

def FindSameElement(arrOne, arrTwo, n):
  for i in range(n - 1):
    for j in range(n - 1):
      if arrOne[i] == arrTwo[j]:
        print("Done!")

第二层循环执行的次数为n * n次，因此该算法的时间复杂度为O(n²)。

二、计算法则

---

代码段有多个不同复杂度的区块，如何计算复杂度呢？

function A(); /*复杂度O(n²)*/
function B(); /*复杂度O(n³)*/
function C() 
{
  A()
  B()
  return
}

函数C的时间复杂度为：

加法原则：O(n³) + O(n²) = O(n³) 

根据时间复杂度的定义，我们只需要关心对结果影响最大的项，其余的直接忽略就好了。

代码段存在调用关系时，如何计算复杂度呢？

function FindEachRoom() /*复杂度O(n)*/
function FindEachBuilding() /*不考虑调用函数，复杂度O(n)*/
  for i = 1 to n
    FindEachRoom()

以上代码相当于一个小区有n幢楼房，每幢楼房有n个房间，我们现在需要遍历每一个房间。遍历楼房的复杂度是O(n)，遍历每幢楼的每个房间的复杂度也是O(n)，那么整体的复杂度就是

乘法原则：O(n) * O(n) = O(n²)

三、常见的时间复杂度

---

• O(1)：数组数据的读取和存储，类似于数学里面的数列，知道下标就可以一次存取。

• O(log(n))：有序数组使用二分法查找某个数据、红黑树操作复杂度。

• O(n) ：以遍历的方式在数组中查找元素。

• O(nlog(n)) ：求两个数组的交集，其中一个为无序数组，使用线性查找，另一个为有序数组，使用二分法查找。

• O(n²) ：求两个无序数组的交集。

四、空间复杂度

---

空间复杂度涉及的因素比较多，这里说一个简单的例子：

//n is the length of array a[] 
int sum(int a[], int n) 
{ 
  int x = 0; // 4 bytes for x 
  for(int i = 0; i < n; i++) // 4 bytes for i 
  { 
     x = x + a[i]; 
  } 
  return x; 
}

数组a[]需要的内存为4*n，变量x、n、i各需要4个字节。因此，需要的总内存为 (4n + 12)字节，则空间复杂度为O(n)。

五、复杂度的均衡

---

事实上，构建代码时，我们经常会使用到数组、链表、HASH表、二叉树、红黑树等。对于不同场景，我们所选择的数据组织形式及相应的算法是不同的，要求高效查询，可以选择数组。对内存有要求时，就该考虑使用链表了。对数据增、删、改、查的偏重不同时，我们选择的算法也会变得不同。

算法终究是需要契合具体应用场景的，有的场景对于存储数据是个低频操作，读取数据却是高频的，那么就需要优先选择读取算法复杂度低的算法。反之亦然。

对于自动驾驶，读取传感器的数据要求效率极高，很多厂商实现上就会采用数组直接映射，读取复杂度O(1)，但是空间复杂度却很高，这其实就是在用空间换时间。

推荐：

推荐阅读：5G是什么

后台回复『复杂度』阅读文章《什么是算法复杂度》

喜欢就『关注』或者『分享』吧。