大 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是什么
后台回复『 复杂度 』阅读文章《什么是算法复杂度》
喜欢就 『 关注 』或者『 分享 』吧。
About The Author
