本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS，因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器，本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI，请尽量通过 HTTPS 访问本站，谢谢！
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录前一修订版后一修订版 | 前一修订版 | ||
| dsa:notes:dahua_ds:2_algorithm [2017/03/23 06:59] – [7.1.算法复杂度分析] haregy | dsa:notes:dahua_ds:2_algorithm [2021/11/11 08:07] (当前版本) – codinghare | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====算法==== | + | ======算法====== |
| 大话数据结构 笔记 第二章\\ | 大话数据结构 笔记 第二章\\ | ||
| <wrap em> | <wrap em> | ||
| - | ===== ===== | + | ---- |
| - | ====1.数据结构和算法==== | + | ====数据结构和算法==== |
| 我们在第一章就说过程序设计的内容包括数据结构和算法。很显然，抛开算法谈数据就是耍流氓了LOL。算法只有和对应的数据结构搭配，才能发挥出程序的最大功效。 | 我们在第一章就说过程序设计的内容包括数据结构和算法。很显然，抛开算法谈数据就是耍流氓了LOL。算法只有和对应的数据结构搭配，才能发挥出程序的最大功效。 | ||
| - | ====2.算法的定义==== | + | ====算法的定义==== |
| 算法就是描**述解决问题的方法**。算法（algorithm）这个词最早出现在波斯数学家阿勒.花刺子密在公元 825 年所写的《印度数字算术》中。如今普遍认可的算法定义是：< | 算法就是描**述解决问题的方法**。算法（algorithm）这个词最早出现在波斯数学家阿勒.花刺子密在公元 825 年所写的《印度数字算术》中。如今普遍认可的算法定义是：< | ||
| \\ | \\ | ||
| \\ | \\ | ||
| 这句话信息量很大，包括了算法的诸多特性。我们接着来看算法的特性。 | 这句话信息量很大，包括了算法的诸多特性。我们接着来看算法的特性。 | ||
| - | ====3.算法的特性==== | + | ====算法的特性==== |
| 算法具有几个基本特性： | 算法具有几个基本特性： | ||
| * **输入、输出**：算法的输入个数大于等于零，而输出个数大于等于一。 | * **输入、输出**：算法的输入个数大于等于零，而输出个数大于等于一。 | ||
| 行 16: | 行 16: | ||
| * **确定性**：算法的每一步步骤必须有确定的含义，不能有二义性。 | * **确定性**：算法的每一步步骤必须有确定的含义，不能有二义性。 | ||
| * **可行性**：算法的每一步都可以通过执行有限次数完成。 | * **可行性**：算法的每一步都可以通过执行有限次数完成。 | ||
| - | ====4.算法设计的要求==== | + | ====算法设计的要求==== |
| 一个好的算法应该包括以下几个特性： | 一个好的算法应该包括以下几个特性： | ||
| - | ===4.1.算法的正确性=== | + | ===算法的正确性=== |
| 正确性：算法至少具有输入、输出和加工处理的无歧义性，能正确的反映需求，能正确的得到问题的答案。这又可以分为几个层次： | 正确性：算法至少具有输入、输出和加工处理的无歧义性，能正确的反映需求，能正确的得到问题的答案。这又可以分为几个层次： | ||
| - 语法正确。 | - 语法正确。 | ||
| 行 25: | 行 25: | ||
| - 算法对于精心选择（边界数据）等有满足要求的结果。 | - 算法对于精心选择（边界数据）等有满足要求的结果。 | ||
| 由此看来算法的正确性跟数学上的证明是有很大的关系的。不过对于我们来说，要验证一个算法对于所有输入的正确性是非常困难的，要通过严格的数学证明来解决。因此，应用中的算法以层次 3 为主。 | 由此看来算法的正确性跟数学上的证明是有很大的关系的。不过对于我们来说，要验证一个算法对于所有输入的正确性是非常困难的，要通过严格的数学证明来解决。因此，应用中的算法以层次 3 为主。 | ||
| - | ===4.2.算法的可读性=== | + | ===算法的可读性=== |
| 好算法的另外一个特征是可读性。 | 好算法的另外一个特征是可读性。 | ||
| \\ | \\ | ||
| \\ | \\ | ||
| 可读性：算法设计的另一个目的是为了方便别的程序员阅读。可读性有助于别人理解算法。 | 可读性：算法设计的另一个目的是为了方便别的程序员阅读。可读性有助于别人理解算法。 | ||
| - | ===4.3.算法的健壮性=== | + | ===算法的健壮性=== |
| 一个好的算法还应该对输入数据不合法的情况做适合的处理。 | 一个好的算法还应该对输入数据不合法的情况做适合的处理。 | ||
| - | ===4.4.时间、空间=== | + | ===时间、空间=== |
| 最后，好的算法还需要具备时间消耗少，空间占用少的特点。 | 最后，好的算法还需要具备时间消耗少，空间占用少的特点。 | ||
| \\ | \\ | ||
| \\ | \\ | ||
| 算法的时间效率是指对于同一个问题，执行时间越少的算法效率越高。而空间占用则指算法运行时对存储空间的占用，占用越低系统资源消耗越少。 | 算法的时间效率是指对于同一个问题，执行时间越少的算法效率越高。而空间占用则指算法运行时对存储空间的占用，占用越低系统资源消耗越少。 | ||
| - | ====5.算法效率的度量==== | + | ====算法效率的度量==== |
| 算法效率的估算大致分两种方法： | 算法效率的估算大致分两种方法： | ||
| * 事后统计 | * 事后统计 | ||
| * 事前估算 | * 事前估算 | ||
| - | ===5.1.事后统计=== | + | ===事后统计=== |
| 都说实践出真知，对算法效率的测试，事后统计是一个很容易想到的办法：通过设计好的测试程序和数据，用计算机计时器对不同算法编制的程序的运行时间进行比较。但是这个办法存在很大的缺陷： | 都说实践出真知，对算法效率的测试，事后统计是一个很容易想到的办法：通过设计好的测试程序和数据，用计算机计时器对不同算法编制的程序的运行时间进行比较。但是这个办法存在很大的缺陷： | ||
| * 依赖测试程序，耗费额外的精力。 | * 依赖测试程序，耗费额外的精力。 | ||
| * 作为评判的标准之一时间受计算机软件、硬件的影响，可能会不精确。 | * 作为评判的标准之一时间受计算机软件、硬件的影响，可能会不精确。 | ||
| * 算法设计的测试数据很困难，而且往往对影响时间关系不大。 | * 算法设计的测试数据很困难，而且往往对影响时间关系不大。 | ||
| - | ===5.2.事前估算=== | + | ===事前估算=== |
| 事前估算的方法就是在计算机变之前，按照**统计方法对算法进行估算**。\\ | 事前估算的方法就是在计算机变之前，按照**统计方法对算法进行估算**。\\ | ||
| \\ | \\ | ||
| 行 62: | 行 62: | ||
| \\ | \\ | ||
| 有没有发现其实运行时间跟消耗的操作次数其实是正比关系？而且我们也可以看到，对于这些不同的算法来说，n 越大，算法体现出来的差异就越明显。 | 有没有发现其实运行时间跟消耗的操作次数其实是正比关系？而且我们也可以看到，对于这些不同的算法来说，n 越大，算法体现出来的差异就越明显。 | ||
| - | ====6.函数的渐进增长==== | + | ====函数的渐进增长==== |
| 从书上的例子我们可以看到，只有当 n 达到一定程度的时候，我们才能得知算法的优劣。因此，我们需要考察函数的**渐进增长效率**，也就是函数的自变量趋于无穷大的时候，算法的运行时间的增长。那么两个函数算法的优劣比较，其实也就为了算法时间增长率的比较。用数学定义来说就是：\\ | 从书上的例子我们可以看到，只有当 n 达到一定程度的时候，我们才能得知算法的优劣。因此，我们需要考察函数的**渐进增长效率**，也就是函数的自变量趋于无穷大的时候，算法的运行时间的增长。那么两个函数算法的优劣比较，其实也就为了算法时间增长率的比较。用数学定义来说就是：\\ | ||
| \\ | \\ | ||
| 行 70: | 行 70: | ||
| \\ | \\ | ||
| 而我们也可以发现，随着 n 逐渐增大，算法中低次项的影响也越来越小（参考书上表格 // | 而我们也可以发现，随着 n 逐渐增大，算法中低次项的影响也越来越小（参考书上表格 // | ||
| - | ====7.算法的时间复杂度==== | + | ====算法的时间复杂度==== |
| 既然明白了算法的时间效率与什么有关，我们就可以用一个标记（notation）来表示算法的时间复杂度了。我们把用大写的 O 来表示算法的复杂度，用 T(n) 来表示算法语句执行的次数。因此我们可以给出算法复杂度的定义：\\ | 既然明白了算法的时间效率与什么有关，我们就可以用一个标记（notation）来表示算法的时间复杂度了。我们把用大写的 O 来表示算法的复杂度，用 T(n) 来表示算法语句执行的次数。因此我们可以给出算法复杂度的定义：\\ | ||
| \\ | \\ | ||
| **算法的时间复杂度记做 T(n)=O(f(n))。它表示随着问题规模 n 的增大，算法执行的时间的增长率与函数本身相同。因此算法的时间复杂度也可以成为算法的渐进时间复杂度，简称时间复杂度。** | **算法的时间复杂度记做 T(n)=O(f(n))。它表示随着问题规模 n 的增大，算法执行的时间的增长率与函数本身相同。因此算法的时间复杂度也可以成为算法的渐进时间复杂度，简称时间复杂度。** | ||
| \\ | \\ | ||
| - | ===7.1.算法复杂度分析=== | + | ===算法复杂度分析=== |
| 我们知道算法复杂度跟函数的最高次项是相关的。因此我们可以对函数做以下的处理： | 我们知道算法复杂度跟函数的最高次项是相关的。因此我们可以对函数做以下的处理： | ||
| - 使用 '' | - 使用 '' | ||
| 行 81: | 行 81: | ||
| - 如果最高次项存在，且不是 '' | - 如果最高次项存在，且不是 '' | ||
| 比如 f(n)=2n2+n+1 的复杂度就是 n2。 | 比如 f(n)=2n2+n+1 的复杂度就是 n2。 | ||
| + | \\ | ||
| + | 具体的的分析主要查看的是数学的知识。不同的方式还有不同的求法，比如迭代用级数算，递归用递归方程算等，这本书比较浅，就不赘述了。 | ||
| + | \\ | ||
| + | \\ | ||
| + | 常见的时间复杂度有： | ||
| + | * 常数阶：O(1) | ||
| + | * 线性阶：O(n) | ||
| + | * 对数阶：O(logn) | ||
| + | * 平方阶：O(n2) | ||
| + | * 立方阶：O(n3) | ||
| + | * 指数阶：O(2n) | ||
| + | ===最坏、平均情况=== | ||
| + | 我们刚才说到的 O 其实代表了算法的最坏时间复杂度，这是一种对算法性能的保证（最坏也就这样了）。而平均情况是很有意义的，因为它是期望的运行时间。不过现实中我们很难通过估算来计算平均复杂度，一般都是通过大量的数据来得出的。因此我们对算法复杂度的分析，默认指定的是最坏复杂度。 | ||
| + | \\ | ||
| + | \\ | ||
| + | \\ | ||
| + | ---- | ||
| + | ~~DISQUS~~ | ||
| + | |||
| + | |||
| + | |||