时间空间复杂度
如何判断一个算法的好坏？
我们需要一种复杂度计算方式，不受计算机性能和程序数据的影响
时间复杂度 BigO
BigO计算表示一个算法的渐进时间复杂度
T(n) = O(f(n))
f(n) 表示代码执行次数之和，O表示正比例关系
复杂度越低代码效率越高
e.g. 1
for (int i = 1; i <= n; i++) {
x++;
}
首先int i = 1为一次运算
其次，每次循环中会分别执行i <= n、i++、x++三次运算
则n次循环下会执行3n次
总共运算1+3n次，那么这个算法复杂度则为O(n)
因为BigO用于表示计算的增长变化趋势，所以当n无限大时，常数1和系数3可忽略不计
e.g. 2
for (int i = 1; i<= n; i++){
for(int j =1; j <= n; j++){
x++;
}
}
在这个双层循环中，内外层各需运行n次
则其时间复杂度为O(n^2^)
当我们将例一例二合起来时，时间复杂度应为多少呢？
你可能会认为是 O(n+n^2^)
然而，当n趋近于无穷大时，线性的n远远小于n^2^
所以此时的时间复杂度应为 O(n^2^)
常见的时间复杂度量级
常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(lognN)
平方阶O(n^2^)
立方阶O(n^3^)
K次方阶O(n^k^)
指数阶(2^n^)
阶乘O(n!)
其他复杂度指标
O(Big O)…………最差情况
Ω(big Omega) …最好情况
Θ(big theta) …….一个算法区间
空间复杂度
内存空间增长的趋势
常用的空间复杂度
O(1) O(n) O(n^2^)
e.g.3 O(1)空间复杂度
int x = 0;
int y = 0;
x++;
y++;
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，此算法空间复杂度为一个常量，可表示为 O(1)
其中x, y所分配的空间不随着处理数据量变化，因此「空间复杂度」为 O(1)
Comments