算法的基本概念

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

数据结构静态的描述了数据元素之间的关系

高效的程序需要在数据结构的基础上设计和选择算法

高效的程序 = 恰当的数据结构 + 合适的算法

算法是对存在的一种解决问题的方法和思想

• 对于算法而言，语言并不重要，重要的是思想

算法的五个特性：

• 有穷性。一个算法必须总在执行有穷步之后结束，且每一步都在有穷时间内完成。

• 确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。

• 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

• 输入。一个算法有0个或多个输入，这些输入取自于某个特定的对象的集合。

• 输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

好的算法应该考虑达到以下目标：

• 正确性。算法应能够正确地解决求解问题。

• 可读性。算法应具有良好的可读性，以帮助人们理解。

• 健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

• 效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程中所需 要的最大存储空间，这两者都与问题的规模有关。

小结：

算法为了解决实际问题而存在

数据结构是算法处理问题的载体

数据结构与算法相辅相成，共同解决问题

算法效率的度量

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

事后统计法

• 比较不同算法对同一组输入数据的运行处理时间

• 缺陷

  • 为了获得不同算法的运行时间必须编写相应程序

  • 运行时间严重依赖硬件以及运行时的环境因素

  • 算法的测试数据的选取相当困难（测试结果受数据规模影响很大）

于是乎我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。

事前分析估算（时间、空间复杂度分析方法）

• 依据统计的方法对算法效率进行估算

• 影响算法效率的主要因素

  • 算法采用的策略和方法

  • 问题的输入规模

  • 编译器所产生的代码

  • 计算机执行速度

大O表示法

算法效率严重依赖于操作（Operation）数量

操作数量的估算可以作为时间复杂度的估算

在判断时首先关注操作数量的最高次项

算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。

**时间复杂度

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记作T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中的基本运算（最深层循环内的语句）的频度与T(n)同数量级，所以通常釆用算法中基本运算的频度 f(n)来分析算法的时间复杂度。因此，算法的时间复杂度也记为：

上式中“O”的含义是T(n)的数量级，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n0，使得当n>=n0时，都满足0 <= T(n) <= C * f(n)。

算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质（如输入数据元素的初始状态）。

例如：在数组A[0...n-1]中，查找给定值K的算法大致如下：

 i=n-1;
 while( i>=0 && (A[i]!=k) )
     i--;  // 语句(3)
 return i;

此算法中的语句(3)（基本运算）的频度不仅与问题规模n有关，还与输入实例中A 的各元素取值及K的取值有关：

• 若A中没有与K相等的元素，则语句(3)的频度 f(n)=n。

• 若A的最后一个元素等于K，则语句(3)的频度f(n)是常数0。

分析时间复杂度的方法：

有以下两条规则 + 一个方法：

• 加法法则：总复杂度等于量级最大的那段代码的复杂度

• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

• 只关注循环执行次数最多的一段代码

  大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。

几种常见时间复杂度实例分析

对于刚罗列的复杂度量级，我们可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!)。

我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。

当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。因此，关于 NP 时间复杂度我就不展开讲了。我们主要来看几种常见的多项式时间复杂度。

1.O(1)

首先你必须明确一个概念，O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。

  int i = 8;
  int j = 6;
  int sum = i + j;

我稍微总结一下，只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。 这个总结有点玄学了，毕竟到底是多少行代码呢 ！

2.O(logn)、O(nlogn)

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

根据我们前面讲的复杂度分析方法，第三行代码是循环执行次数最多的。所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的:

 

所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2x=n 求解 x 这个问题我们想高中应该就学过了，我就不多说了。x=log2n，所以，这段代码的时间复杂度就是 O(log2n)。

现在，我把代码稍微改下，你再看看，这段代码的时间复杂度是多少？

 ​
  i=1;
  while (i <= n)  {
    i = i * 3;
  }

根据刚刚讲的思路，很简单就能看出来，这段代码的时间复杂度为 O(log3n)

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？

我们知道，对数之间是可以互相转换的， 就等于，所以 ，其中 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 。所以，就等于 。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 。

如果你理解了我前面讲的 O(logn)，那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则吗？如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

3.O(m+n)、O(m*n)

 int cal(int m, int n) {
   int sum_1 = 0;
   int i = 1;
   for (; i < m; ++i) {
     sum_1 = sum_1 + i;
   }
 ​
   int sum_2 = 0;
   int j = 1;
   for (; j < n; ++j) {
     sum_2 = sum_2 + j;
   }
 ​
   return sum_1 + sum_2;
 }

从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。空间复杂度分析

时间复杂度分析练习

练习一

练习二

函数t里面少了个i++;。。。

练习三

空间复杂度

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

算法的空间复杂度S(n)，定义为该算法所耗费的存储空间，它是问题规模n的函数。渐近空间复杂度也常简称为空间复杂度，记作S(n)=O(g(n))。

一个上机程序除了需要存储空间来存放本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间，若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。

算法原地工作是指算法所需辅助空间是常量，即O(1)。

小结：算法的复杂度

• 时间复杂度

  • 算法运行后对时间需求量的定性描述

• 空间复杂度

  • 算法运行后对空间需求量的定性描述

*四个复杂度分析方面的知识**

大部分(80%)代码的复杂度分析: 按照上节课将的 加法法则,乘法法则,足以应付. 少部分代码(20%)代码的复杂度分析: 此部分代码会随着输入数据的顺序,位置的不同, 时间复杂度存在量级的差距.在这种情况下,我们才需要使用到最好时间复杂度,最坏时间复杂度.平均时间复杂度,均摊时间复杂度去分析这部分代码.

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

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

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

4. 均摊时间复杂度就是一种特殊的平均时间复杂度

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

思考

有人说，我们项目之前都会进行性能测试，再做代码的时间复杂度、空间复杂度分析，是不是多此一举呢？而且，每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？你怎么看待这个问题呢？

我不认为是多此一举，渐进时间，空间复杂度分析为我们提供了一个很好的理论分析的方向，并且它是宿主平台无关的，能够让我们对我们的程序或算法有一个大致的认识，让我们知道，比如在最坏的情况下程序的执行效率如何，同时也为我们交流提供了一个不错的桥梁，我们可以说，算法1的时间复杂度是O(n)，算法2的时间复杂度是O(logN)，这样我们立刻就对不同的算法有了一个“效率”上的感性认识。

当然，渐进式时间，空间复杂度分析只是一个理论模型，只能提供给粗略的估计分析，我们不能直接断定就觉得O(logN)的算法一定优于O(n), 针对不同的宿主环境，不同的数据集，不同的数据量的大小，在实际应用上面可能真正的性能会不同，个人觉得，针对不同的实际情况，进而进行一定的性能基准测试是很有必要的，比如在统一一批手机上(同样的硬件，系统等等)进行横向基准测试，进而选择适合特定应用场景下的最有算法。

综上所述，渐进式时间，空间复杂度分析与性能基准测试并不冲突，而是相辅相成的，但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时间复杂度程序，所以在实际编程中，时刻关心理论时间，空间度模型是有助于产出效率高的程序的，同时，因为渐进式时间，空间复杂度分析只是提供一个粗略的分析模型，因此也不会浪费太多时间，重点在于在编程时，要具有这种复杂度分析的思维。

我的思考：

大O表示法都是渐进式的，和数据规模有关往往取的极限值，但是某个特定输入范围或者环境下，这时有局限性。此时有些看似复杂的算法可能会有更好的性能， 另外通过测试找出性能瓶颈，以便优化基础代码，从指令级上进行优化。

关于性能测试

总的来说，性能测试其实是一个很复杂的过程。需要结合不同的方面正确分析需求，根据需求设计出合理的测试场景，定义出性能测试的指标，并且在测试中选择合适的工具进行测试，并且结合测试的多项结果进行分析和trouble shooting。

大O表

https://www.bigocheatsheet.com/

本文参考文献：

1 http://cskaoyan.com/forum.php 王道论坛数据结构资料

2 王争老师的数据结构与算法之美

3 狄泰的数据结构课程