算法时间复杂度定义

在进行算法分析时，语句总的执行次数 是关于问题规模 n 的函数，进而分析 随 n 的变化情况并确定 的数量级。算法的时间复杂度，也就是算法的时间量度，记作：。它表示随问题规模 n 的增大，算法执行时间的增长率和 的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。其中 是问题规模 n 的某个函数。

这样用大写 来体现算法时间复杂度的记法，称之为大O记法

一般情况下，随着 n 的增大， 增长最慢的算法为最优算法

推导大 O 阶方法

推导大 O 阶：

1. 用常数 1 取代运行时间中的所有加法常数

1. 在修改后的运行次数函数中，只保留最高阶项

1. 如果最高阶项存在且不是 1，则去除与这个项相乘的常数

得到的结果就是大 O 阶

常数阶

与问题的大小无关（n 的多少），执行时间恒定的算法，称之为具有 的时间复杂度，又叫常数阶

注：不管这个常数是多少，都记作 ，而不能是 、 等其他任何数字

线性阶

for(int i=0;i<n;i++){  // 时间复杂度为 O(1) 的程序步骤}

上面的时间复杂度是 ，因为循环体的代码需要执行 n 次。

对数阶

int count=1;while(count<n){  count=count*2;}

由于每次 count 乘以 2 之后，距离 n 更近一分。也就是说，有多少个 2 相乘后大于 n，则会退出循环。由

得到

。所以这个循环的时间复杂度为

，所以这个循环的时间复杂度为

平方阶

for(int i=0;i<n;i++){   for(int j=0;j<n;j++){     // 时间复杂度为 O(1) 的程序步骤   }}

如果外层循环次数改为了 m，时间复杂度就变成了

for(int i=0;i<m;i++){   for(int j=0;j<n;j++){    // 时间复杂度为 O(1) 的程序步骤  }}

for(int i=0;i<n;i++){   for(int j=i;j<n;j++){    // 时间复杂度为 O(1) 的程序步骤   }}

由于当 i=0 时，内循环执行了 n 次，当 i=1 时，执行了 n-1 次，·····当 i=n-1 时，执行了 1 次。所以总的执行次数为：

根据推导大 O 阶的方法，最终上面的代码的时间复杂度为

常见的时间复杂度

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