【数据结构与算法】时间复杂度和空间复杂度

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

推导大O阶

推导攻略:

• 用常数1取代运行时间中的所有加法常数
• 在修改后的运行次数函数中,只保留最高阶项
• 如果最高阶项存在且不是1,则去除与这个项相乘的常数

常数阶

常数阶用O(1)表示

线性阶

线性阶用O(n)表示
示例:如下代码的时间复杂度即为O(n)

int I ,n = 100, sum = 0;
for(I = 0 ; I < n; I++){
   sum = sum + I;
}

平方阶

平方阶用O(n²)表示
示例:如下代码的时间复杂度即为O(n²)

int I , j , n = 100;
for (I = 0; I < n; I++){
   for(j = 0; j < n; j ++ ){
   printf("666")
   }
}

对数阶

对数阶用O(logn)表示
示例:如下代码的时间复杂度即为O(logn)

int I = 1, n = 100;
while(I < n){
 I = I * 2
}
//由于2^x = n ,所以x = log(2)n

常见时间复杂度

时间复杂度	术语	例子
O(1)	常数阶	123
O(n)	线性阶	2n+3
O(n²)	平方	3n²+4n+5
O(logn)	对数阶	3log(2)n + 5
O(nlogn)	nlogn阶	2n + 3nlog(2)n + 10
O(n³)	立方阶	n³+3n²+4n+5
O(2^n)	指数阶	2^n

常见时间复杂度耗费时间从小到大依次是: O(1)<O(logn)<(O(n))<O(nlogn)<O(n²)<O(n³)<O(2^n)

空间复杂度

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:

S(n)=O(f(n))