为什么要进行算法分析

在设计一个算法时,我们往往会进行算法分析。之所以要做这一件事,是因为总是希望设计出来的算法能够占用更少的硬件资源,同时运行时间短。但实际上,随着现在计算机的发展,内存等硬件资源已经不再是算法效率的瓶颈,就好比以前的手机是几百MB的内存,现在是4GB,8GB的内存。所以在进行算法分析的时候,我们更关心的是算法的运行时间。

如何分析算法运行时间

RAM模型

实际上,因为每个人的电脑,CPU,内存都不会完全相同,同样一个算法跑在不同的机器上运行时间也不同。所以为了分析算法运行时间,我们事先做了一个“标准”的计算机模型(叫做RAM模型)来大致估计一个算法的运行时间。

在这台计算机上,我们假设

  • 使用单处理器
  • 指令一条条运行,不会并发运行
  • 每条指令所需的时间都为常量

基于上述假设,我们才能开始分析算法运行时间。

如何分析算法运行时间

实例讲解

有了上面的假设,我们使用一段代码是讲解如何分析算法运行时间。

由于我们假设每条指令所需时间都为常量,所以这里设该常量为c

1
2
3
4
count = 0;                     /* 运行次数:1     时间:c */              
for(k=1; k<=n; k++){           /* 运行次数:n+1(最后跳出循环需要判断一次) 时间:(n+1)*c */
	count++;                   /* 运行次数:n     时间:n*c */
}

所以该段代码的运行时间为:$ T(n) = (2n+2)×c $

这个常量看起来有点多余,所以在严蔚敏的《数据结构》这本书中,常量取的是1,而$T(n)$于是就变成了$T(n)=2n+2$

备注:她自己又定义了频度的概念,实际上说白了就是一个语句的执行次数,所以T(n)就被定义为算法中所有语句的频度之和。垃圾!!!!!非要定义这么复杂

分析上面代码的运行时间为:$ T(n) = (2n+2)×c $,我们需要知道三件事:

  • 算法的运行时间和输入的n有关,即和问题的规模有关
    • 比如排序这个问题,小规模序列排序和大规模序列排序,就算使用相同的排序算法,大规模序列肯定花费时间高
  • 算法的运行时间和输入的内容有关

    • 比如排序这个问题,对同样长度的两个序列进行排序,如果输入的序列本来就排好序了,那么花费的时间肯定比没排好序的序列少
  • 人们往往关心的是算法运行时间的上界,也就是这个算法最慢不会慢到哪里去(即:最坏情况)。

大O记号的引入

通过上面的实例,我们可以精确计算在ram模型下一个算法的运行时间,但是我们需要分析每行代码的运行次数,这样其实根本没必要。我们只需要关心这个算法在最坏情况下的时间数量级,比如这个算法是10ms数量级的,还是1000ms数量级的。(不会去关心这个算法的精确运行时间是1001ms,还是1005ms)。所以我们引入了大O记号来分析这个算法的运行时间的数量级,也叫做时间复杂度。

图像

数学定义

$O(g(n)) = 集合[ f(n)|存在正常数c和n_0使得所有的f(n)满足:当n \geq n_0时,均有0<f(n) <cg(n) ]$

记作$O(g(n))=f(n)$

理解

  • $O(g(n))​$ 是一个集合,里面的元素是$f(n)​$ ,不要认为$f(n)​$的表达式就是$O(g(n))​$,$O(g(n))=f(n)​$只是个记号而已
  • 这个集合的理解:当n大于某个值时,我们可以保证$f(n)$ 是小于若干倍的$g(n)$
  • 这个记号描述了当输入大于某个规模以后,算法运行时间的最坏情况是怎么样的,之所以要说大于某个规模,是因为不同算法,在小规模的n上,运行时间差别不好,我们关心的是对于大规模输入时,算法的表现
  • 对于某一个算法:$T(n) = O(n)$的含义是:

    • 这个算法的运行时间不会高于若干倍的$n$
  • 此时,我们称该算法的时间复杂度为$O(n)$

例子

若某一个算法的$T(n) = 3n+5$, 则其时间复杂度为:$O(n)$

证明:

由 $3n+5 < 4n$ 解得 $n>5$

所以存在正常数4,当n>5时,有$T(n) = 3n+5 < 4n$

故$T(n) = O(n)$

分析时间复杂度的实用技巧

已知T(n)求时间复杂度

  • 忽略所有低阶项,最高阶项的系数,剩下的就是O(多少)
  • eg: $T(n) = 3n^3+2n^2+5$
  • 忽略低阶项$2n^2+5$,忽略最高阶项系数3
  • 得到$T(n) = O(n^3)$

给定代码段,直接求时间复杂度

笨方法是:计算T(n),再求复杂度

一些技巧是:

  • 一个for循环为$O(n)$
  • 多个for循环嵌套为 $O(n^{嵌套层数})$

  • 顺序语句:运行时间最大的作为时间复杂度

    • 比如一个代码段有两个for循环,其中一个是二层for循环,那么整个代码时间复杂度为$O(n^2)$

一些分析T(n)和时间复杂度的例子

  • to be filled