算法学习-复杂度分析

风尘

文章目录

  1. 1. 时间复杂度
    1. 1.1. 常数时间O(1)
    2. 1.2. 线性时间O(n)
    3. 1.3. 平方时间O(n^2)
    4. 1.4. 对数时间O(logn)
    5. 1.5. 指数时间O(2^n)
    6. 1.6. 常用时间复杂度
  2. 2. 空间复杂度

时间复杂度

算法时间复杂度,即算法的时间量度,采用大O记法( O()O() ):

T(n)=O(f(n))T(n) = O(f(n))

表示随问题规模 nn 的增大,算法执行时间的增长率和 f(n)f(n) 的增长率相同,其中 f(n)f(n) 是问题规模 nn 的菶函数。
通常,随着 nn 的增大,T(n)T(n) 增长最慢的算法为最优算法。

推导时间复杂度大 O 方法:

  1. 因为常数项对函数的增长速度影响不大,所以用常数 1 取代运行时间中的所有加法常数。如:
     
    T(n)=2T(n) = 2 // 把常数 2 用 1 取代,所以时间复杂度为 O(1)O(1)
     
  2. 因为高次项对于函数的增长速度的影响最大( n3>n2>nn^3 > n^2 > n ),所以在修改后的运行次数函数中,只保留最高项。如:
     
    T(n)=n3+n2+29T(n) = n^3 + n^2 + 29 // 只保留最高项 n^3,所以时间复杂度为 O(N3)O(N^3)
    T(n)=n+29T(n) = n + 29 // 只保留最高项 n,所以时间复杂度为 O(n)O(n)
     
  3. 因为函数的阶数对函数的增长速度影响最显著,所以如果最高项存在且不是1,则去除与这个项相乘的常数
     
    T(n)=3n3T(n) = 3n^3 // 最高项存在且不是 1,所以去除相乘常数后时间复杂度为 O(N3)O(N^3)

常数时间O(1)

1
2
3
4
5
void aFunc(){
int sum = 0,n = 100; // 执行一次 时间复杂度 O(1)
sum = (1+n) * n/2; // 执行一次 时间复杂度 O(1)
printf("%d",sum); // 执行一次 时间复杂度 O(1)
}

函数 afunc 运行次数的函数是 T(n)=3T(n) = 3。根据大 O 推导方法,把常数项 3 改为 1。然后保留最高项,其最高项就是常数项,所以这个算法的时间复杂度为 O(1)O(1)

线性时间O(n)

1
2
3
4
5
void aFunc(int n){
for(int i = 0; i < n; i++) { // 循环次数 n ,时间复杂度为 O(n)
printf("Hello World!"); // 时间复杂度 O(1)
}
}

循环的时间复杂度为 O(n)O(n),循环体内时间复杂度为 O(1)O(1),则这个循环的时间复杂度为 O(n×1)O(n × 1),根据推导方法第三步去掉最高项相乘的常数,即 O(n)O(n)

平方时间O(n^2)

1
2
3
4
5
6
7
void aFunc(int n){
for(int i = 0;i < n; i++){ // 循环次数为 n,时间复杂度为 O(n)
for(int j = 0; j < n; j++){ // 循环次数为 n,时间复杂度为 O(n)
printf("Hello World!"); // 时间复杂度为 O(1)
}
}
}

此时间复杂度为 O(n×n×1)O(n × n × 1),即O(n2)O(n^2)

1
2
3
4
5
6
7
8
void aFunc(int n){
int i,j;
for(i = 0; i < n; i++){ // 循环次数为 n,时间复杂度为 O(n)
for(j = i; j < n; j++){ // 注意 j = i而不是0
printf("Hello World!"); // 时间复杂度为 O(1)
}
}
}

i=0i = 0 时,内循环执行 nn 次,当 i=1i = 1时,执行了 n1n-1次,……当 i=n1i = n -1时,执行了 11 次。所以总执行次数为:

n+(n1)+(n2)+...+1=n(n+1)2=n22+n2n + ( n - 1 ) + ( n - 2 ) + ... + 1 = \frac{n ( n + 1 )}{ 2 } = \frac{ n^2 }{2} + \frac{ n }{ 2 }

大O推导方法,保留最高阶项 n22\frac{ n^2 }{ 2 },然后去除这个项相乘的常数 12\frac{ 1 }{ 2 },得出时间复杂度为 O(n2)O(n^2)

对数时间O(logn)

1
2
3
4
5
6
7
void aFunc(int n){
int count = 1;
while(count < n){
count = count * 2;
printf("Hello Word!");
}
}

从此例中可以看出当循环执行 2x=n2^x = n,即x=log2nx = log_2n 次时结束。所以时间复杂度为 O(logn)O(logn) (底数2可以省略)

指数时间O(2^n)

1
2
3
4
5
6
7
long aFunc(int n){
if(n <= 1){
return 1;
} else {
return aFunc(n - 1) + aFunc( n - 2 );
}
}

此代码可以看出,T(0)=T(1)=1T(n)=T(n1)+T(n2)+1T(0) = T(1) = 1,T(n) = T(n - 1) + T(n - 2) + 1。通过归纳法证明,当 n>=1n >= 1 时,T(n)<(5/3)nT(n) < (5/3)^n,当 n>4n > 4 时,T(n)>=(3/2)nT(n) >= (3/2)^n,所以简化后的时间复杂度为 O(2n)O(2^n)

常用时间复杂度

图:常用的时间复杂度图:常用的时间复杂度

常用的时间复杂度所耗费时间从小到大依次是:

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(n2)O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^2)

时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,深入到函数进行分析。

空间复杂度

空间复杂度是对一个算法在运行过程中临时战胜存储空间大小的量度。
计算公式:S(n)=O(f(n))S(n) = O(f(n)) nn 为问题规模,f(n)f(n) 为语句关于 nn 所占存储空间的函数。

比如插入排序的空间复杂度是 O(1)O(1),而一般递归算法就要有 O(n)O(n)的空间复杂度,因为每次递归都要存储返回信息。

有时也可以用空间换时间的方法,如要判断某年是不是闰年,可以写一个算法,每次给一个年份来计算出结果,还有另一个方法就是,事先建立一个有 2050 个元素的数组,然后把所有年份按下标数字对应如果是闰年,此数组项值为1,反之为0。如此一来就可以实现闰年判断。