算法复杂度

来自于:极客时间,数据结构与算法之美

复杂度分析

时间复杂度

大 O 表示法:表示代码执行时间随数据规模增长的变化趋势。

只关注循环次数最多的一段代码

1
for(i =1;i<n;i++)

这行代码被执行了 n 次,所以是 O(n)

总复杂度等于量级最大的那段代码的复杂度

嵌套代码的时间复杂度等于嵌套内外代码复杂度的乘积

1
2
3
4
5
6
7
8
9
10
11
for(i =1;i<n;i++){
i = i + f(i)
}

public int f(int i){
int sum = 0;
for(i =0;i<n;i++){
sum = sum + i;
}
return sum;
}

时间复杂度为: O(n^2)

常见的时间复杂度

O(1)

只要不存在循环,递归。时间复杂度就是 o(1)

O(longn),O(nlongn)

1
2
3
4
int i = 1;
while(i <= n){
i = i * 2;
}

i 的值依次是: 2 2^2 2^3 2^4 …. 2^n

所以: 2^x = n, x = long 2 n

简化为: O(longn).

如果是两层循环。最外层是 fori 循环,则时间复杂度就是 :O(nlongn)

O(m + n) O(m * n)

类似上面的例子,现在是有两个变量而已。

空间复杂度

表示算法的存储空间与数据规模之间的增长关系。

时间复杂度

不同的时间复杂度

最坏时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 最坏时间复杂度
* <p>
* arr 无序 不重复
*
* @return
*/
private int badTimeComplexity() {
int[] arr = {1, 2, 3, 454};
int pos = -1;
for (int i = 0; i < arr.length; i++) {
if (i == 3) {
pos = i;
}
}
return pos;
}

总是遍历完 arr ,所以时间复杂度是 O(n)

最好时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 最坏时间复杂度
* <p>
* arr 无序 不重复
*
* @return
*/
private int goodTimeComplexity() {
int[] arr = {1, 2, 3, 454};
int pos = -1;
for (int i = 0; i < arr.length; i++) {
if (i == 3) {
pos = i;
break;
}
}
return pos;
}

最好的情况就是,第一个元素就匹配到,所以 为 O(1)

平均时间复杂度

要查找的变量 x 在数组中的位置,有 n + 1 中情况(在数组中 n 和不在数组中 1),每种情况下,查找需要遍历的元素累加起来,然后除以 n + 1。然后,得到需要遍历元素个数的平均值。

平均时间复杂度推导公式

ps: 推导半天,高中知识都忘光了。

简化一下:也是 O(n)

但是没考虑概率问题。

假设:在数组中和不在数组中的概率都是 1/2,另外,在数组中的元素的 n 个位置的概率也是一样的,为 1/n,所以,在数组中的概率为 1/2n(概率的乘法法则)。如果,把每种情况发生的概率考虑进去,则平均时间复杂度就变成了:

加权的时间复杂度

简化一下:也是 O(n)

均摊时间复杂度

什么玩意啊。。。

Look at your mood.