数据结构----算法复杂度分析

• 时间复杂度

1. 常数阶

int i = 0;int n = 100; 
printf("test"); 
printf("test");
printf("test"); 
printf("test"); //算法时间复杂度为O(1)

int i = 0;int n = 100; int sum = 0;
for(i=0; i



　　  3、平方阶
　　　　O(n^2)：随着问题规模n的增大，对应的计算次数成抛物线增长
　　　　

int i = 0, j = 0;int n = 100; int sum = 0;
for(i=0; i O(n^2)
//算法时间复杂度为O(n^2)




　　  4、对数阶
　　　　O(log（n))：随着问题规模n的增大，对应的计算次数成对数线增长
　　　　

int i = 1; int n = 100;
while(i < n)
{
    i = i * 2;
}//2^x = n --->x = log(n)
//算法时间复杂度为O(log(n))




　　  5、总结
　　　　常用时间复杂度耗费时间从小到大排列：
　　　　O(1) < O(log(n)) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)


空间复杂度


O(n)表示基本代码占据的存储空间