[数据结构与算法]时间复杂度求解--算法效率的度量

? 一直都说算法很重要，写出一个好算法不容易。那么有怎么样来评价一个算法的好坏呢？算法的评价指标主要有四个：正确性、可读性、健壮性、高效率与低存储量。其中的高效率，一般是通过时间复杂度来进行衡量。但时间复杂度却是困扰众多学子的一大”难题“，许多刚学数据结构的同学都被难到了。本文，我们就一起来学习下，通过几个案例，来彻底理解时间复杂度。

1.为什么是时间复杂度

? 算法的执行时间需要通过依据该算法编写的程序在计算机上运行时所消耗的时间来度量的。而度量一个程序的执行时间通常有两种方法。

1. 事后统计方法：根据算法编写程序，然后在计算机上执行，得到执行时间。
2. 事前分析估算方法：通过理论分析，在问题求解的规模下，得到”运行工作量“，也就是时间复杂度。

? 一个用高级程序语言辨析的程序在计算机上的运行时所耗时间取决于下面五个因素：

• 依据算法选用何种策略；
• 问题的求解规模，例如求100以内还是1000以内的素数；
• 书写程序的语言，对于同一种算法，实现语言的级别越高，执行效率就越低；
• 编译程序所产生的机器代码的质量；
• 机器执行指令的速度。

? 显然，同一个算法使用不同的语言实现、用不同的编译程序进行编译、在不同的计算机上运行时，执行的耗时都有差异。这表明使用绝对的时间单位来衡量算法的效率是不合适的。而且使用事后统计方法，还需要先将算法实现，并在计算机上执行，加大了工作难度。

? 撇开这些与计算机硬件、软件有关的因素，可以认为一个特定的算法”运行工作量“的大小，只依赖于问题的规模(通常用整数量n来表示)，或者说，他是问题规模的函数。

? 为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一两种对于所研究的问题来说是基本操作的原操作，以改基本操作重复执行的次数作为算法的时间复杂度。

? 我们以一个小栗子来简单介绍下，下面是两个N*N矩阵相乘的算法，”乘法“运算是”矩阵相乘问题的基本操作。整个算法的执行时间与该基本操作重复执行的次数n³成正比，记作：
$$T(n)=O(n^3)$$

for(i=1; i<-n; ++i)
  for(j=1; j<=n; ++j){
    c[i][j] = 0;
    for(k=1; k<=n; ++k)
      c[i][j] += a[i][k] * b[k][j]
  }

2.时间复杂度的概念

? 一般情况下，算法中的基本操作执行的次数是问题规模n的某个函数f(n)，算法的时间量度记做
$$T(n)=O(f(n))$$
他表示随着问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。

? 除了上述之外，还有一个其他的概念，如下所示：

• 最坏时间复杂度：指在最坏情况下，算法的时间复杂度；
• 平均时间复杂度：指所有可能输入实例在等概率条件出现的情况下，算法的期望运行时间；
• 最好时间复杂度：指在最好情况下，算法的时间复杂度。

? 我们以排序问题为例，最坏的情况是指所有的元素都不在指定的位置上，或者说是逆序的；最好情况就是输入的序列本身就是按照要求(升序、降序)有序的；平均情况是考虑所有的输入情况下，平均下来的时间复杂度。

? 一般情况下，我们总是考虑在最坏情况下的时间复杂度，即分析最坏情况以估算算法执行时间的一个上节，保证算法的运行时间不会比它更长。

? 在分析一个程序的时间复杂度是，有以下两条准则：

1. 加法规则
   $$T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(Max(f(n),g(n)))$$

2. 乘法规则
   $$T(n)=T1(n)?T2(n)=O(f(n))?O(g(n))=O(f(n)?g(n))$$

常见的渐进时间复杂度有：
$$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

3.空间复杂度

? 空间复杂度，相比于时间复杂度就简答的多了。

? 算法的空间复杂度S(n)，定义为该算法所耗费的存储空间，它是问题规模n的函数。记做:
$$S(n)=O(g(n))$$
? 一个程序出了需要存储空间来存放本身所用的指令、常数和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间，若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间，否则应同时考虑输入本身所需的空间（和输入数据的表现形式有关）。

? 若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。如交换两个变量的值，代码需要定义一个临时变量，那么空间复杂度就是O(1)，属于原地工作。部分排序算法，就属于此类，如交换排序。

4.一些例子

? 光说不练，假把式。下面我们来通过一些典型的案例，来一起看下时间复杂度到底是如何计算的。

void funA(int n) {
  // 循环次数为 n
  for(int i = 0; i < n; i++) {
    //基本运算
    printf("Hello, World!\n");
  }
}

? 上面问题中，基本运算和问题规模n有关，输出语句执行的次数等于i++的次数，因此T(n) = O(n).

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

? 上面问题中，基本运算是i=i*2，设其执行时间为T(n)，则2^T(n)<=n，T(n) <= log₂n = O(log₂n).

void funC(int n) {
  int count=0;
  for(int k=1; k<=n; k*=2)
    for(int j=1; j<=n; j++)
      count++;
}

? 这个问题中有两层循环，需要单独分析。内层循环条件j<=n与外层循环的变量无关，由前两个例子可知，内层循环的时间复杂度为O(n)；外层循环条件为k<=n，可知循环次数为2^k<=n，即k<=log₂n，外层循环的时间复杂度为O(log₂n)。根据时间复杂度的乘法规则可知，该程序的时间复杂度T(n) =T₁(n) * T₂(n) =O(n) * O(log₂n) = O(nlog₂n)。

void funD(int n) {
    // 第一部分时间复杂度为 O(log2n)
    int i=1;
    while(i<=n)
      i = i*2;
    // 第二部分时间复杂度为 O(n)
    for(int j = 0; j < n; j++) 
        printf("Hello, World!\n");
}

? 上面问题中，可以看到，两个循环是顺序执行的，根据加法规则可知，总的时间复杂度T(n) =T₁(n) + T₂(n) =O(n) + O(log₂n) = Max(O(n), O(log₂n)) = O(n)。当程序段中出现分支结构（if）时，也是相同的，其执行频率最高的为该算法的时间复杂度。

4.一些练习

? 上面讲了一些基本的例子，下面我们通过一些题目来简单练一练。

1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是_________。

x=2;
while(x<n/2)
  x=2*x

? 在程序中，基本运算为x=2*x，设该语句执行了t次，2^t+1>=n/2，t>=log₂(n/2) - 1 = log₂n - 2，因此时间复杂度为O(log₂n).

2.求整数n(n>=0)阶乘的算法如下，其时间复杂度是_________.

int fact(int n){
  if(n<=1) return 1;
  return n * fact(n-1);
}

? 本题中，是就n的阶乘的递归问题，不过也没有想象的这么复杂，n!=n*(n-1)…1，共执行n次乘法操作，故T(n) = O(n)。

3.求斐波那契数列的递归算法如下，其时间复杂度是_________.

int fibonacci(int n){
  if(n==1 || n=2)
    return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

? 本题中，递归变得稍微复杂了些，由题可知，F(n) = F(n-1) + F(n-2)，相求F(n-1)需要求出F(n-2)和F(n-3)的值，这种递归的求F(n)的值，有点类似于二叉树，且可以知道二叉树的高度为n，求F(n)需要的计算量可以约等于于二叉树的节点数，即每个节点都需要计算。这样可以知道T(n) = 1 + 2 + 4 … + 2^n-1 = 2ⁿ-1，因此O(n) = 2ⁿ.

4.下面算法的时间复杂度为_________.

void funE(int n){
  int i=0,s=0;
  while(s<n){
    ++i;
    s=s+i;
  }
}

? 由题可以发现，基本操作为++i、s = s+i，且都与循环的结束条件有关，问题似乎是变得复杂了，但是难不倒你。假设循环执行m次结束，则由s₁ = 1; s₂ = 1+2=3; s₃ = 1+2+3=6…;s_m = 1+2…+m=m(m+1)/2，则有m(m+1)/2 + K=n，(其中K为起修正作用的常数，可以理解为执行m+1次，s_m+1>=n，s_m + K=n)，求值可得：
$$m=\frac{?1+\sqrt{8n+1?8K}}{2}$$
由此可知T(n) = f(n) =$\frac{?1+\sqrt{8n+1?8K}}{2}$= O($\sqrt{n}$)，时间复杂度为 O($\sqrt{n}$)。

5.总结

? 通过以上分析，我们总结出计算一个算法的时间复杂度的具体步骤如下：

1. 确定算法中的基本操作以及问题的规模。
2. 根据基本操作的执行情况计算出规模n的函数f(n)，并确定时间复杂为T(n) = O(f(n)中增长最快的项/此项系数).

? 对于时间复杂度求解，许多同学一眼能看出程序的时间复杂度，但是无法将其推到过程规范的表达出来。其实这类问题分为两种形式，其求解思路如下：

? 一是循环主体中的变量参与循环条件的判断。此类问题应当找出主体语句中与T(n)成正比的循环变量，将之带入条件中进行计算。例如练习题中的4.1，x*2的次数正是主体语句的执行次数T(n)，因此有2^t+1>=n/2，最后时间复杂度为O(log₂n)。

? 二是循环主体中的变量与循环条件无关。此类问题可采用数学归纳法，或直接累计循环次数；多层循环时从内到外分析，忽略单步语句、条件判断语句，只关注主体语句的执行次数。此类问题有可分为递归和非递归程序。

• 递归程序一般采用公式进行递推，如例题4.2、4.3
• 非递归程序比较简单，可以直接累计次数。

? 又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主自己进行整理并结合自身的理解进行总结，如果有什么错误，还请批评指正。

? 本专栏为数据结构知识，喜欢的话可以持续关注，如果本文对你有所帮助，还请还请点赞、评论加关注。

? 有任何疑问，可以评论区留言。

关注博主即可阅读全文