常碰到的时间复杂度
其中指数阶和阶乘阶都属于十分低效的复杂度量级，应该尽量避免。
时间复杂度.png
下面这段代码的时间复杂度为log(n)
//这段代码的时间负责度就是log(n)
i=1;
while (i <= n) {
i = i * 2;
}
最好与最坏情况下的时间复杂度
- 最好时间复杂度
- 最坏时间复杂度
- 平均时间复杂度
最好时间复杂度和最坏时间复杂度都很好理解，那么什么是平均复杂度呢？
我们先看下面代码：
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
- 最好时间复杂度为O(1)，最坏时间复杂度为O(N)；
-
平均时间复杂度计算如下：
要查找的变量 x 在数组中的位置，有 n+1 种情况（n种找到、1种未找到），这n+1种情况分别查找1、2、3....n-1、n、n次，那么平均时间复杂度如下：
计算过程.png
如果假设找到与没找到的概率都为1/2，那么加权平均时间复杂度（期望时间复杂度）为：
加权平均时间复杂度计算.png
平均时间复杂度和加权平均时间复杂度都为O(n)，我们在考虑时间复杂度时只考虑量级的变化，并不考虑k值。
