04.时间复杂度和空间复杂度-02

算法时间复杂度

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

在以上定义中，把指令执行次数看做时间，这样用O()体现时间复杂度的记法称之为大O记法，一般情况下，随着输入规模n的增大，T(n)增长最慢的算法被称为最优算法。

推导大O阶方法

如何分析一个算法的时间复杂度？也就是如何推导大O阶？

通过上一章的测试，我们知道

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

int sum = 0;
int n = 100;
System.out.println("Hello World");
System.out.println("Hello World");
System.out.println("Hello World");
System.out.println("Hello World");
System.out.println("Hello World");
System.out.println("Hello World");
sum = (1 + n) * n / 2;

这段代码的大O是多少？

初学者常犯的错误认为有多少语句，大O就为多少，认为是O(9)

但是分析一下，根据我们的概念“T(n)是关于问题规模n的函数”来说，但是本段代码的输出语句与n没有关系，唯一有关系的只有sum = (1 + n) * n / 2，所以记作O(1)即可，也就是我们总结的第一条，“用常数1取代运行时间中的所有加法常数”

线性阶

一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模n的增长，对应的计算次数也成线性增长

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

上面代码时间复杂度为O(n)，因为循环n次（忽略所有循环条件判断）

平方阶

int n = 100;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    System.out.println("Hello World");
  }
}

外层循环每执行一次，内部循环执行n次，外层共要执行n次，所以一共执行 $n*n$ 次，所以这段代码时间复杂度为O( $n^2$ )，那么如果为三层循环，则时间复杂度为O( $n^3$ )

在刚刚的代码中，两层循环次数是一样的，比较容易计算，但是如果对代码进行变化

int n = 100;
for (int i = 0; i < n; i++) {
  for (int j = i; j < n; j++) {
    System.out.println("Hello World");
  }
}

分析：当i=0时，内部循环执行n次，当i=1时，内部循环执行n-1次……当i=n-1时，内部循环执行1次，所以总执行次数为：
n + (n-1) + …… + 1 = (n + 1) * n / 2 = $n^2/2 + n/2$
根据我们总结的方法，因为没有常数，所以第一条忽略，第二条只保留最高项 $n^2/2$ ，第三条去除与最高项相乘的常数，最终得O( $n^2$ )

对数阶

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

由于每次i * 2后，i就距离n更进一步，假设有X个2相乘后大于等于n，就会退出循环，于是由 $2^x=n$ 的到 $x=log_2n$ ，所以这个循环的时间复杂度为O( $logn$ )

其实理解大O推导并不难，主要是对数列的一些相关运算，需要用到一定的数学知识，对于想考研的朋友，需要强化自身的数学知识，尤其是数列方面。但是对于想增长自身编程能力的朋友，大概知道规律就好，不需要再数学的概念上纠结。

内容均来源于学习资料，在学习过程中进行记录，如有侵权联系作者进行删除

Change the world by program

最后编辑于：2019.12.27 00:30:04