数据结构与算法之时间复杂度(笔记)

2017-04-28  本文已影响0人  iStorm

数据结构:

算法:

时间复杂度

举例:
int sum = 0, n =100;

printf("This a test!");

printf("This a test too!");

sum = (1+n)*n/2;

//时间复杂度为:O(1)
int i, n = 100, sum = 0;

for(i = 0; i < n; i++){

sum = sum + i;

}

//时间复杂度为:O(n)
int i, j, n = 100;

for(i = 0; i < n; i++){
    
    for(j = 0; j < n; j++){
        printf("This a second test!");      
    }
}

//时间复杂度为:O(n^ 2)
- 理解:

   n 等于 100 时,即外层循环每执行一次,内层循环就执行 100 次,从程序退出来,需要执行 100*100 次,即 n^2 所以这段代码的时间复杂度为O(n^ 2)。
   
- 总结:
  
  循环的时间复杂度等于循环体的复杂度乘以该循环运行次数。
int i, j, n = 100;

for( i = 0; i < n; i++){

    for( j = i; j < n; j++){
        
        printf("This a third test!");
        
    }
}

//时间复杂度为:O(n^ 2)
- 分析:

  当 i = 0 时,内循环执行 n 次,当 i = 1 时,内循环执行 n - 1 次......当 i = n -1 时,内循环执行 1 次,总的执行次数为:
  - n + (n -1) + (n -2) + (n -3) + (n -4) +......+1 = n*(n + 1)/2
int i = 1, n = 100;

while(i < n){
    
    i = i * 2;
}

//时间复杂度为:O(log n )
- 分析:
   由于每次 i * 2 之后,距离 n 更近一步,假设有 x 个 2 相乘大于或等于 n 则退出循环
   2 ^ x = n
   x = log2^n
int i, j;

for( i = 0; i < n; i++ ){

function(i);
}

void function(int count){

printf("%d",count);
}

//function函数的时间复杂度为:O(1)
//整体的时间复杂度为:O(n)

//假设:
void function(int count){

    int j;

    for( j = count; j < n; j++){
        printf("%d",j);
    }
}

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

常见时间复杂度:

表达式 时间复杂度 类型
2017428 O(1) 常数阶
3n+4 O(n) 线性阶
3n^2+4n+5 O(n^2) 平方阶
3log2^n + 4 O(logn) 对数阶
2n+2n^2+4n+6 O(nlogn) nlogn阶
n3+2n2+4n+6 O(n^3) 立方阶
2^n O(2^n) 指数阶
上一篇 下一篇

猜你喜欢

热点阅读