abstract

本文介绍算法相关的基本概念,算法特点,算法指标,分析基础算法和简单抽象算法性能

介绍复杂度以及相关符号(时间复杂度和空间复杂度,以时间复杂度为主)

复杂度量级之间的比较以及部分关系的简单证明,介绍初等数学公式或一些恒等式在算法时间复杂度上的分析用途

算法的基本概念

算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。此外，一个算法还具有下列五个重要特性：
1)有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2)确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
3)可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4)输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
5)输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

算法指标

通常，设计一个“好”的算法应考虑达到以下目标：

1)正确性。算法应能够正确地解决求解问题。
2)可读性。算法应具有良好的可读性，以帮助人们理解。
3)健壮性。算法能对输入的非法数据做出反应或处理，而不会产生莫名其妙的输出。
4)高效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

算法的效率

算法的效率是通过时间复杂度和空间复杂度来描述的

问题规模(输入规模)

不考虑计算机的软硬件等环境因素，影响算法时间代价的最主要因素是问题规模。问题规模是算法求解问题输人量的多少，是问题大小的本质表示，一般用整数表示。问题规模n对不同的问题含义不同，

例如，在排序运算中n为参加排序的记录数，在矩阵运算中n为矩阵的阶数，在多项式运算中n为多项式的项数，在集合运算中n为集合中元素的个数，在树的有关运算中n为树的结点个数，在图的有关运算中n为图的顶点数或边数。显然，n越大算法的执行时间越长。

有时输入不止一个对象,例如对两个长度分别为$m,n$的升序链表,将它们合并为长度为$m+n$的降序链表,那么评估算法的复杂度等操作不仅取决于$m,n$中的一个,而是两个都要考虑;(这个例子中,利用头插法做降序合并,需要比较两个链表尾部元素(从后面往前比),每次比较可确定出一个元素的链接位置,在最坏的情况下需要两个输入链表依次比较,需要比$n+m-1$次

• 例如两个链表中的元素链分别为(1,3,5,7),(2,4,6)),那么要执行的比较次数为$4+3-1=6$次

由于$m+n⩽2\cdot \max (m,n)$,所以时间复杂度为$O(\max (m,n))$

语句频度

一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。

一条语句的重复执行次数称作语句频度（FrequencyCount）由于语句的执行要由源程序经编译程序翻译成目标代码，目标代码经装配再执行，因此语句执行一次实际所需的具体时间是与机器的软、硬件环境（如机器速度、编译程序质量等）密切相关的。

所以，所谓的算法分析并非精确统计算法实际执行所需时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。

设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有语句频度之和来度量。

复杂度

先介绍相关的概念和例子,再介绍算法复杂度

算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，以考察算法的时间和空间效率。一般情况下，鉴于运算空间较为充足，故将算法的时间复杂度作为分析的重点。

频度

• 频度:一个语句的频度是指该语句在算法中被重复执行的次数。
• 频度之和:算法中所有语句的频度之和记为 $T(n)$，它是该算法问题规模 $n$ 的函数

例

假设a,b,c是$n$阶矩阵(可以视为二维数组)

/* 分析2个n阶矩阵乘法算法的时间复杂度 
为了便于讨论，这里约定最外层的循环(for)记为for1,第二层为for2，以此类推。
此外进一步细分可以分为for_x判断句和for_x循环体,其中x表示第x层循环。一般的,在不考虑多重循环带来的差异叠加,前者要比后者多执行一次
一般的,对于一个有限循环而言,判断是否进入循环体的条件判断语句执行的次数是比循环体执行次数要多一次,因为最后一次循环体的执行后还需要再做一次判断才能够确认循环(体)是否继续执行;比如while-do;for-loop
而do-while这种现执行后判断的循环情况会有所不同,通常是循环体的执行次数和判断条件次数一致
*/
for (int i = 0; i < n; i++) //频度:n+1 (这里循环变量i的取值范围是0..n)一共是n+1次执行(最终i=n,而不是n-1,尽管i=n时不会执行内部的循环体)
{for (int j = 0; j < n; j++) // 频度:n*(n+1);这是一个内部循环(二重),分析for2循环判断语句,循环变量j取值范围是0..n,同样是n+1次执行判断;考虑到外重循环的循环体会执行n次,而每次该for语句会执行n+1次判断,因此该语句的频度为n*(n+1){c[i][j] = 0;//频度:n*n;该语句作为for2的循环体,会执行n次,考虑到for2又是for1的循环体会执行n次,因此频度为n*nfor (int k = 0; k < n; k++) //频度:n*n*(n+1);for3是第三重循环,首先for3作为for2的循环体中的语句,会执行n*n次,而for3本身又是循环,并且k的取值范围是0..n(共n+1个值),也就是会执行n+1次判断,因此频度为n*n*(n+1){c[i][j] += a[i][k] * b[k][j];//频度为n*n*n;作为三重循环的循环体,for3会执行}}}
//上述代码的所有语句频度之和为2n*n*n+3n*n+2n+1

这就是说上述的$n$阶矩阵乘法的频度之和为$f(n)$=$2n^3+3n^2+2n+1$,这是一个$n^3$级别复杂度的算法(时间上)

输入数据状态

算法的时间复杂度不仅依赖于问题的规模 $n$，也取决于待输入数据的性质（如输入数据元素的初始状态）。例如，在数组 A[0…n−1] 中，查找给定值 k 的算法大致如下:

(1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3)    i--;
(4)return i;

该算法中语句 3（基本运算）的频度不仅与问题规模 $n$ 有关，而且与下列因素有关:
① 若 A 中没有与 k 相等的元素，则语句 3 的频度 $f(n)=n$。
② 若 A 的最后一个元素等于 k，则语句 3 的频度 $f(n)$ 是常数 0。

算法的时间复杂度👺

对于上述矩阵乘法这种较简单的算法,可以直接计算出算法中所有语句的频度

但对于稍微复杂一些的算法,则通常是比较困难的,即便能够给出,也可能是个非常复杂的函数。

因此,为了客观 地反映一个算法的执行时间,可以只用算法中的"基本语句"的执行次数来度量算法的工作量。

定义

算法执行时间的数量级称为算法的渐近时间复杂度，$T(n)=O(f(n))$,它表示随着问题规模$n$的增大，算法执行时间的增长率和$f(n)$的增长率相同，简称时间复杂度。

一般$f(n)$表示算法的基本语句的频度,但是分析时间复杂度时,会对$f(n)$做形式上的简化,比如取$f(n)$中随$n$增长最快的项,并且将其系数置为1作为时间复杂度的度量

例如$f(n)$=$a_1{n}^m+a_2{n}^{m-1}+\cdots +a_m$的时间复杂度为$O(n^m)$;

基本语句

基本语句:所谓"基本语句"指的是算法中重复执行次数和[算法的执行时间]成正比的[语句],它对算法运行时间的贡献最大。(类似于线性主部)

渐进性能

通常,算法的执行时间是随问题规模增长而增长的,因此对算法的评价通常只需考虑其随问题规模增长的趋势。这种情况下,我们只需要考虑当问题规模充分大时,算法中基本语句的执行次数在渐近意义下的阶。

如例矩阵的乘积算法,当n趋向无穷大时,显然有
$$\underset{n\to \infty }{\lim }f(n)/n^3=\underset{n\to \infty }{\lim }(2n^3+3n^2+2n+1)/n^3=2$$
即当n充分大时,$f(n)和n^3$之比是一个不等于零的常数。即$f(n)和n^3$是同阶的,或者说$f(n)$和$n^3$ 的数量级(Order of Magnitude)相同。

符号O和渐进时间复杂度 数量级

上面的例子中,我们用"O"来表示数量级,记作$T(n)=O(f(n))=O(n^3)$。

一般情况下,算法中基本语句重复执行的次数是问题规模$n$的某个函数$f(n)$,算法的时间量度记作
$$T(n)=O(f(n))$$
它表示随问题规模n的增大,算法执行时间的增长率和$f(n)$的增长率相同,称作算法的 渐近时间复杂度,简称时间复杂度(Time Complexity)。

严格定义符号O

先不管函数$T(n),f(n)$表示的具体含义,从抽象角度做定义

数学符号"O"的严格定义为: 若$T(n)$和$f(n)$是定义在正整数集合上的两个函数,则式子:$T(n)=O(f(n))$表示存在正的常数$C$和$n_0$,使得当$n\ge n_0$时都满足$0\le T(n)\le Cf(n)$。
该定义说明了函数$T(n)$和$f(n)$具有相同的增长趋势，并且$T(n)$的增长至多趋向于函数$f(n)$的增长。

符号“O”用来描述增长率的上限，它表示当问题规模$n>n_0$时，算法的执行时间不会超过$f(n)$

理解符号O

注意:符号O并不定义函数,而是描述了某两个函数间满足的一种关系;

环境话说,O的定义不是描述$O(n)=\cdots$这种函数定义,而是描述已有函数间的关系(其实$T(n)=O(f(n))$这个式子中的等号病不同于常规意义上的等号,有集合的含义在里面)

对于一个确定的算法,若该算法复杂度记为$O(f(n))$,那么任务就是确定$f(n)$,我通过判断$f(n)$来判断算法复杂度到底如何

在描述一个算法的时间复杂度时,通常会带上符号$O()$,(如果是其他指标,会有其他符号,可以参考算法导论)

并且$f(n)$通常是取尽可能简单的式子,比如关于$n$的幂,甚至是一个常数(1),这种情况称为常量阶

如果一个算法的时间复杂度是常量阶,那么意味着该算法的时间复杂度和输入规模$n$没有关系,算法性能很高

反之,如果一个算法与输入规模无关(比如遍历1到$n_0$内的整数),那么即使$n_0$再大($n_0$是定死的),也和$n$无关,它的复杂度仍然是$O(1)$,也就是常量阶的;如果$n_0$不是定死的,而是由输入$n$决定的,那么复杂度变为$O(n)$,线性阶

其次是对数级别的时间复杂度,根据对数函数的特点,随着规模$n$的增大,它的增长速度比变慢,比一次函数还要慢,这种情况下我们也说该算法性能高,如果是多项式级别的复杂度,我们仍然认为它的性能还可以;如果是指数级别甚至更高,那么说明这个算法性能是相当糟糕的

相关描述

• 在相同规模$n$下,复杂度为$O(n)$的算法在时间上总是优于复杂度为$O(2^n)$的算法

  • 这句话容易让人误解,单从文字描述上看,我认为这句话是错误的,或者是不严谨的,应该要强调$n\to \infty$或者$n$足够大的时(类比于极限的概念)
  • 时间复杂度指的是渐进时间复杂度,描述的是$n\to \infty$时的算法需要的时间的数量级

• 我们可以说时间复杂度为$O(n)$的算法在时间上要优于复杂度为$O(2^n)$的算法,指的是渐进性能欠着要优于后者

  • 在$n$是有限值时,复杂度较高的算法执行的速度是有可能快于复杂度低的算法的,例如应用最广泛的排序算法快速排序,它的时间复杂度(最坏情况下)是$O(n^2)$的,其时间复杂度比$O(n{\log }_{2}n)$的算法要高,但是输入规模不是特别大的情况下,其排序速度有可能是快于地复杂度的其他排序算法

分析算法时间复杂度的基本方法👺

找出所有语句中语句频度最大的那条语句作为基本语句，计算基本语句的频度得到问题规模$n$的某个函数$f(n)$，取其数量级用符号O表示即可。(事实上,并不总是要计算出精确的$f(n)$,例如有时我们推出$f(n)$满足的方程,(方便起见令$i=f(n)$,也就是第$i=t$次算法终止,或者说基本语句最后一次执行是第$i$次)

比如$i(i+1)/2<n$,估算或简化等号左边为$i^2$,等号右边的系数2可以简化为1,并且把$<$改为$=$,得到$f(n)$的数量级为$f(n)=n^{\frac{1}{2}}$,算法的时间复杂度为$O(n^{\frac{1}{2}})$

具体的数量级取$f(n)$的随$n$增长最快的项,并且置其系数为1;

一般在保持正确的情况下,我们尽可能让表示数量级的表达式简单一些,使其反映的算法复杂度容易更直观,例如$2n^3+3n^2+2n+1$,当$n\to \infty$时它和$n^3+kn+b$的商的极限都是2,而把$f(n)$取得简单一些会更直观,比如取$n^3$来表示算法时间复杂度的数量级

根据高等数学的知识,如果一个算法(基本语句)的频度函数$f(n)$是一个$m$次多项式(最高次项为$m$次),那么该算法的时间复杂度$T(n)=O(n^m)$

这里$T(n)$是等号左边的式子,函数符号不一定用$T$,而且很多地方不强调等号左边,而直接说等号右边

对于给定的一段代码分析复杂度基本步骤参考👺

• 常见的问题是基于循环(可能是多重循环)

• 一般是确定最内层循环变量或关键表达式的变化次数,因为它往往反映了基本语句的执行频度

• 循环变量的取值范围或取值集合的元素数量的确定是关键,关键表达式向最后一个取值靠近的速度体现了算法的时间复杂度

  • 第$i$次进入循环	循环变量(关键表示)取值
    $i=1$	$v_1$
    $i=2$	$v_2$
    …	…
    $i=t$	$v_t$

    其中$t$用$i$本身表示也可以

• 例如初始$x=2$每次循环x=x*2,当$x<n$时结束,那么$x$的前几次执行结果为$x=4,8,16,...$,即$2^2,2^3,2^4,...$;从而大致抽象处执行次数i和$x$的关系:$x_i=2^{i+1}$,则由$2^{i+1}=n$求出$i$关于$n$的表达式,就能反映算法的复杂度:本例中该算法的复杂度为$O({\log }_{2}n)$,其中$i={\log }_{2}n-1$,舍弃常熟部分,得到${\log }_{2}n$

• 对于多重循环，一般利用乘法规则,依次分析各层循环的复杂度,然后做乘法

符号补充说明👺

在算法导论等算法文献中,有关于算法分析符号的丰富说明,详情另见资料

三种情况下的复杂度

最坏时间复杂度是指在最坏情况下，算法的时间复杂度。

平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。

最好时间复杂度是指在最好情况下，算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

时间复杂度分析规则

在分析一个程序的时间复杂性时，有以下两条规则:

1. 加法规则: $T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$

2. 乘法规则: $T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$

常见的复杂度阶

$$O(1)<O({\log }_{2}n)<O(n)<O(n{\log }_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

中学时我们有一个大致的结论:指数函数增长的比幂函数要快(指数函数的底大于1,且自变量趋于无穷时)

考虑到当$n\to \infty$指数函数(算法中通常以$2$为底)的增长速率要大于幂函数$n^{\alpha }$($\alpha >0$,即便$\alpha$很大),他们的反函数${\log }_{2}n$和$n^{\frac{1}{\alpha }}$做比较,前者的增长速度要慢于后者($n\to \infty$)

简化和推广结论
$$O(1)<O({\log }_{2}n)<O(n^{k_1})<O(n{\log }_{2}n)<O(n^{k_2})<O(2^n)<O(n!)<O(n^n)$$
其中$k_1\in (0,1]$,$k_2\in (1,u)$,其中$u$是一个有限大的常数

指数函数和幂函数的增长速率

从高等数学的角度简单分析两个无穷大:$a^n$,$n^k$,$(a>1,k>0)$两个函数(数列)哪个增长的快

我们把问题转换为论证$\underset{n\to \infty }{\lim }\frac{n^k}{a^n}$是否为0的问题上,令$p(n)=\frac{n^k}{a^n}$

• 任意$a>1$，$\underset{n\to \infty }{\lim }\frac{n}{a^n}=0$,这是显然的,可以用洛必达法则得出
• 对$p(n)$做变形,$p(n)=n^k/a^n=(n/a^{(n/k)}{)}^k$，显然$\underset{n\to \infty }{\lim }\frac{n^k}{a^n}$=$0$

这说明,在上述条件下,指数函数比幂函数增长的快

综合示例

下列程序段的时间复杂度是()。

int sum=0; 
for (int i=1;i<n;i*=2) for (int j=0;j<i;j++) sum++; 

对于单层循环如for(j=0;j<i;j++) sum++;,可以直接数出执行次数为i,因此可将多层循环转换成多个并列的单层循环,且列出每个单层循环如下(假设循环变量$i$最后进入循环体的取值为$2^l$,则$l$为循环变量的幂次,也就是说第$l$次进入循环是最后一次,且$l={\log }_{2}n$):

循环变量i	单层循环语句	单层循环执行次数
1	for (j=0;j$<$1;j++)	1
$2^1$	for (j=0;j$<$2;j++)	2
$2^2$	for (j=0;j$<$2$^{2}$;j++)	4
$\cdots$	$\cdots$	$\cdots$
2${}^l$	for (j=0;j$<$2$^{l}$;j++)	2${}^l$

进入外层循环的条件是$i<n$,当循环结束时,循环变量的幂满足$i$=$2^l$$<$n$\le$ 2${}^{l+1}$。总执行次数T=$1+2^1+2^2+\cdots +2^l=2^{l+1}-1$,即$n-1\le T$且$T<2n-1$,所以时间复杂度为O(n)。

这个例子中涉及等比数列求和$S_l=\frac{a_n\cdot 2-1}{2-1}$=$2^{l+1}-1$

1. 循环主体中的变量参与循环条件的判断

在用于递推实现的算法中，首先找出基本运算的执行次数 $x$ 与问题规模 $n$ 之间的关系式，解得 $x=f(n)$，$f(n)$ 的最高次幂为 $k$，则算法的时间复杂度为 $O(n^b)$。例如，

#例1. 
int i=1;
while(i<=n)i=i*2;#例2. 
int y=5;
while((y+1)*(y+1)<n)y=y+1;

在例1中，设基本运算 $i=i\ast 2$ 的执行次数为 $t$，则 $2^t\le n$，解得 $t\le {\log }_{2}n$，故 $T(n)=O({\log }_{2}n)$。

在例2中，设基本运算 $y=y+1$ 的执行次数为 $t$，则 $t=y-5$，且 $(t+5+1)(t+5+1)<n$，解得 $t<\sqrt{n}-6$，即 $T(n)=O(\sqrt{n})$。

第$i$次	$y=y+1$	关于$i$的表达式
1	y=5+1=6	$y=1+5$
2	y=6+1=7	$y=2+5$
…	…	…
t	y=t+5	$y=t+5$

把$y=t+5$带入到判断式求出关于$t$表示为关于$n$的表达式取最高项即可

递归算法的复杂度举例

要求解递归方程 $T(n)=\{\begin{array}{ll}1,& n=1\\ 2T(n/2)+n,& n>1\end{array}$ 的时间复杂度

为简单起见,设$n$是$2$的整数次幂

主定理计算递归算法的时间复杂度

我们可以使用主定理（Master Theorem）来分析。

主定理提供了一种解决形如 $T(n)=aT(n/b)+f(n)$ 的递归关系的方法，其中 $a\ge 1$ 和 $b>1$ 是常数，$f(n)$ 是一个渐进正函数。

在给定的递归方程中，我们有 $a=2$, $b=2$, 和 $f(n)=n$。根据主定理，我们需要比较 $n^{{\log }_{b}a}$ 和 $f(n)$：

• $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n$
• $f(n)=n$

因为 $f(n)$ 和 $n^{{\log }_{b}a}$ 是同阶的，即 $f(n)=\Theta (n^{{\log }_{b}a})$，根据主定理的第二种情况，时间复杂度为 $T(n)=\Theta (n^{{\log }_{b}a}\log n)=\Theta (n\log n)$。

因此，该算法的时间复杂度的级别（或阶）是 $O(n\log n)$。

观察法

$$T(n)=\{\begin{array}{ll}1,& n=1\\ 2T(n/2)+n,& n>1\end{array}$$

设$n=2^k(k\ge 0)$(1)，则$k={\log }_{2}n$(2)

常规思路是获得$T(n)$关于$n$的表达式(或者其他单个字母的表达式),并且等号右边不含$T$函数

根据所给定义做迭代推到观察有:

$T(n)$=$T(2^k)=2T(2^{k-1})+2^k$=$2(2T(2^{k-2})+2^{k-1})+2^k$=$2^{2}T(2^{k-2})+2\times 2^k$，类似的,进一步可得$2^{3}T(2^{k-3})+3\times 2^k$

由此可得一般递推公式:$T(n)$=$T(2^k)=2^{i}T(2^{k-i})+i\times 2^k$，

令$i=k$,进而得$T(2^k)=2^{k}T(2^0)+k\times 2^k$=$2^k+k\times 2^k$=$(k+1)2^k$，分别代入式(1),(2),即$T(n)$=$({\log }_{2}n+1)n$=$n{\log }_{2}n+n$,其中第一项增长最快,取第一项，也就说$T(n)$的复杂度为$O(n{\log }_{2}n)$。

数学公式在算法时间复杂度分析上的应用

• 平方和公式或朱世杰恒等式在时间复杂度分析上的应用

for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x++;

这个算法是一个三层循环,我们隐约可以知道算法的复杂度为$O(n^3)$

严谨一点需要分析x++;语句的频度,$f(n)$=${\sum }_{i=1}^n{\sum }_{j=1}^i{\sum }_{k=1}^{j}1$=${\sum }_{i=1}^n{\sum }_{j=1}^{i}j$=${\sum }_{i=1}^n{\sum }_{j=1}^{i}j$=${\sum }_{i=1}^n\frac{1}{2}(i+1)i$=${\sum }_{i=1}^n\left(\genfrac{}{}{0ex}{}{i+1}{2}\right)$=${\sum }_{i=2}^{n+1}\left(\genfrac{}{}{0ex}{}{i}{2}\right)$=$\left(\genfrac{}{}{0ex}{}{n+2}{3}\right)$=$\frac{(n+2)(n+1)n}{6}$,其最高项为$\frac{1}{6}{n}^3$

有由此可见,算法的时间复杂度为$O(n^3)$

算法的空间复杂度

关于算法的存储空间需求，类似于算法的时间复杂度，我们采用渐近空间复杂度（Space Complexity)作为算法所需存储空间的量度，简称空间复杂度，它也是问题规模n的函数，记作：
$$S(n)=O(f(n))$$
一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。

其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。

原地工作

若算法执行时所需要的辅助空间相对于输入数据量而言是个常数(但不是说不需要辅助空间)，则称这个算法为原地工作，辅助空间为O(1)

有的算法需要占用临时的工作单元数与问题规模有关