Question

时间复杂度定义

• 在进行算法分析时 ,语旬总的执行次次 T(n) 是关子问题规模 n 的函数，进而分析 T(n)n 的变化情况并确定 T（n）的数量级。
• 一般情况下，随着 n 的增大,T(n) 增长最慢的算法为最优算法
• 算法的时间复杂度也就算法的度量，记作： T（n）=O(f(n)) .它表示随问题规模 n 的增大，算法执行时间增长率和 f(n) 的增长率相同，乘坐算法的渐进时间复杂度。其中 f(n) 是问题规模 n 的某个函数
• 这样用大写 O() 来体现算法时间复杂度的记法，我们称之为大 0 记法 。
• 常见的有常数阶 O（1），线性阶 O（n），对数阶 O（logn），平方阶 O（n2）

推导大 O 阶方法

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

常数阶

高斯求和：求 1+2+3+4+5+6…+n 结果集

public static void main(String[] args) {
    int  sum = 0,n = 100; // 执行一次
    sum = (1 + n) *(n/2); // 执行一次
    System.out.println(sum); //执行一次
}

这个算法的运行次数函数是 f(n) =3 .根据我们推导大 0 阶的方法，第一步就是
把常数项 3 改为 1 在保留最高阶项时发现，它根本没有最高阶项，所以这个算法的 O(1).

线性阶

• 线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个 特定语句或某个语句集运行的次数。因此，我们要分析算法的复杂度，关键就是要分 析循环结构的运行情况。

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

 /* 时间复杂度为 O(1) 的程序步骤序列 */
}

它的循环的时间复杂度为 O(n), 因为循环体中的代码须要执行 n 次。

对数阶

int count = 1; 
while (count < n){
 count = count * 2;
 /* 时间复杂度为 O(1) 的程序步骤序列 */
}

• 由于每次 count 乘以 2 之后，就距离 n 更近了一分 。 也就是说，有多少 n 个 2 相乘后大于 ,则会退出循。由 2x2^x2x=n 得到 x=log2n。 所以这个循环的时间复杂度为 O(logn) 。
• 二分查找算法的时间复杂度就是 O(logn)。O(logn) 的意思是以 log 为底数（你如果采用二分法，那么就会以 2 为底数，三分法就会以 3 为底数）比如当数据增大 256 倍时，耗时只增加 8 倍：

O(logn)=O(log256)

2x2=4                  //第 1 次
2x2x2=8                //第 2 次
2x2x2x2=16             //第 3 次
2x2x2x2x2=32           //第 4 次
2x2x2x2x2x2=64         //第 5 次
2x2x2x2x2x2x2=128      //第 6 次
2x2x2x2x2x2x2=256(n)   //第 7 次 7 个 2 相乘后=n
2x2x2x2x2x2x2x2>n      //第 8 次 个 2 相乘后大于

O(nlogn) 同理，就是 n 乘以 logn，当数据增大 256 倍时，耗时增大 256*8=2048 倍。这个复杂度高于线性低于平方。归并排序就是 O(nlogn) 的时间复杂度。