数据结构(2) 算法

短命女 2022-02-03 06:45 261阅读 0赞

# **算法定义**： #

解决特性问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

![img][]

# 算法具有五个基本特性。 #

<table> 
 <thead> 
  <tr> 
   <th>输入</th> 
   <th>算法具有零个或多个输入</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>输出</td> 
   <td>算法至少有一个或多个输出</td> 
  </tr> 
  <tr> 
   <td>有穷性</td> 
   <td>算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且一个步骤在可接受的时间内完成。</td> 
  </tr> 
  <tr> 
   <td>确定性</td> 
   <td>算法的每一个步骤都具有确定的含义，不会出现二义性。</td> 
  </tr> 
  <tr> 
   <td>可行性</td> 
   <td>算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。</td> 
  </tr> 
 </tbody> 
</table>

# 算法设计要求： #

<table> 
 <thead> 
  <tr> 
   <th>正确性</th> 
   <th>算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>大体分为以下四个层次： 1 算法程序没有语法错误。 2 算法程序对于合法的输入数据能够产生满足要求的输出结果。 <strong>3 算法程序对于非法的输入数据能够得出满足规格说明的结果。</strong> 4 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。 一般情况，以层次3作为一个算法是否正确的标准。</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>可读性</td> 
   <td>算法设计的另一目的是为了便于阅读、理解和交流。</td> 
  </tr> 
  <tr> 
   <td>健壮性</td> 
   <td>当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。</td> 
  </tr> 
  <tr> 
   <td>时间效率高和存储量低</td> 
   <td>设计算法应该尽量满足时间效率高和存储量低的需求。</td> 
  </tr> 
 </tbody> 
</table>

# 算法效率的度量方法 #

### 事后统计方法 ###

主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

缺陷：

1.  必须依据算法事先编制好程序，需要花费大量的时间和精力。
2.  时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。
3.  算法的测试数据设计困难，程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在小的测试数据面前得不到体现。

基于事后统计方法有上述缺陷，不予采纳。

### 事前分析估算方法 ###

在计算机程序编制前，依据统计方法对算法进行估算。

<table> 
 <thead> 
  <tr> 
   <th>算法执行时间的受影响因素</th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1 算法采用的策略、方法</td> 
   <td>算法好坏的根本</td> 
  </tr> 
  <tr> 
   <td>2 编译产生的代码质量</td> 
   <td>软件支持</td> 
  </tr> 
  <tr> 
   <td>3 问题的输入规模</td> 
   <td>输入量的多少</td> 
  </tr> 
  <tr> 
   <td>4 机器执行指令的速度</td> 
   <td>硬件性能</td> 
  </tr> 
 </tbody> 
</table>

PS: 抛开与计算机硬件、软件有关的因素。**一个算法的运行时间，依赖于算法的好坏和问题的输入规模**。

我们不关心编写程序的设计语言，也不关心程序跑在什么计算机中，我们只关心它所实现的算法。**最终，在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤**。

综上所述，测定运行时间最可靠的方法就是计算对运行时间有消耗的**基本操作的执行次数**。运行时间与这个计数成正比。  
而我们在分析一个算法的运行时间时，重要的是把**基本操作**的数量**与输入规模关联**起来，即基本操作的数量必须**表示成输入规模的函数**。

<table> 
 <thead> 
  <tr> 
   <th>举例：1 + 2 + 3 + … + n 求和算法</th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>算法</td> 
   <td>输入规模</td> 
   <td>基本操作的执行次数（输入规模的函数）</td> 
  </tr> 
  <tr> 
   <td>遍历1到n累加</td> 
   <td>n</td> 
   <td>f(n) = n</td> 
  </tr> 
  <tr> 
   <td>(1 + n) * n / 2</td> 
   <td>n</td> 
   <td>f(n) = 1</td> 
  </tr> 
 </tbody> 
</table>

![img][img 1]

# 函数的渐近增长 #

**函数的渐近增长：给定两个函数 f(n) 和 g(n)，如果存在一个整数 N，使得对于所有的 n > N，f(n) 总是比 g(n) 大，那么，我们说 f(n) 的增长渐近快于 g(n)**。

两个算法函数进行比较时，随着 n 的增长，我们发现如下几点规律：

1.  **加法常量可以忽略**。
2.  **与最高次项相乘的常数并不重要**。
3.  **最高次项的指数大的，函数随着 n 的增长，结果也会增长的特别快**。

**综上所述，判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数**。

判断一个算法的好坏，少量的数据是不能做出准确判断的。  
**某个算法，随着n的增大，它会越来越优于另一个算法，或者越来越差于另一个算法**。  
即事前估算方法的理论依据，通过算法时间复杂度来估算算法时间效率。

##  ##

## 算法时间复杂度 ##

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

这样用大写O()来体现时间复杂度的记法，称之为**大O记法**。

# 推导大O阶方法 #

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

# 常见的时间复杂度 #

<table> 
 <thead> 
  <tr> 
   <th>执行次数函数 f(n)</th> 
   <th>阶 O(f(n))</th> 
   <th>非正式术语</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>12</td> 
   <td>O(1)</td> 
   <td>常数阶</td> 
  </tr> 
  <tr> 
   <td>6n^3 + 2n^2 + 3n + 4</td> 
   <td>O(n3)</td> 
   <td>立方阶</td> 
  </tr> 
  <tr> 
   <td>3n^2 + 2n + 1</td> 
   <td>O(n^2)</td> 
   <td>平方阶</td> 
  </tr> 
  <tr> 
   <td>5log2(n) + 20</td> 
   <td>O(logn)</td> 
   <td>对数阶</td> 
  </tr> 
  <tr> 
   <td>2n + 3nlog2(n) + 19</td> 
   <td>O(nlogn)</td> 
   <td>nlogn阶</td> 
  </tr> 
  <tr> 
   <td>6n^3 + 2n^2 + 3n + 4</td> 
   <td>O(n^3)</td> 
   <td>立方阶</td> 
  </tr> 
  <tr> 
   <td>2^n</td> 
   <td>O(n^2)</td> 
   <td>指数阶</td> 
  </tr> 
 </tbody> 
</table>

常用时间复杂度所耗费的时间 从小到大依次是:  
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

# 最坏情况与平均情况 #

查找一个有n个随机数字数组的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为 O(1) ,但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是 O(n) ,这是最坏的一种情况。

**最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。**

**平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。**

对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为**平均时间复杂度**。另一种方法是计算最坏情况下的时间复杂度，这种方法称为**最坏时间复杂度**。**一般在没有特殊说明的情况下，都是指最坏时间复杂度**。

# 算法空间复杂度 #

我们在写代码时，完全可以用空间来换取时间。

**算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作： S(n) = O(f(n)) ,其中， n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数。**

通常，我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度时”，通常指时间复杂度。

[img]: /images/20220203/7f10487595d7489aac16e470577a0f0d.png
[img 1]: /images/20220203/7123bfa225214c0d89e17f469f2267e3.png