======算法======
大话数据结构 笔记 第二章\\
<wrap em>我的笔记均包含大量个人理解内容，存在一定偏差。如果您发现错误，请留言提出，谢谢！</wrap>
----
====数据结构和算法====
我们在第一章就说过程序设计的内容包括数据结构和算法。很显然，抛开算法谈数据就是耍流氓了LOL。算法只有和对应的数据结构搭配，才能发挥出程序的最大功效。
====算法的定义====
算法就是描**述解决问题的方法**。算法（algorithm）这个词最早出现在波斯数学家阿勒.花刺子密在公元 825 年所写的《印度数字算术》中。如今普遍认可的算法定义是：<wrap em>算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每一条指令表示了一个或多个操作。</wrap>
\\
\\
这句话信息量很大，包括了算法的诸多特性。我们接着来看算法的特性。
====算法的特性====
算法具有几个基本特性：
  * **输入、输出**：算法的输入个数大于等于零，而输出个数大于等于一。
  * **有穷性**：算法必须在有限的步骤内完成，并且每一步的步骤要在可接受的时间内完成。
  * **确定性**：算法的每一步步骤必须有确定的含义，不能有二义性。
  * **可行性**：算法的每一步都可以通过执行有限次数完成。
====算法设计的要求====
一个好的算法应该包括以下几个特性：
===算法的正确性===
正确性：算法至少具有输入、输出和加工处理的无歧义性，能正确的反映需求，能正确的得到问题的答案。这又可以分为几个层次：
  - 语法正确。
  - 对合法输入的数据产生正确的结果。
  - 对非法的输入能产生满足规定的结果。
  - 算法对于精心选择（边界数据）等有满足要求的结果。
由此看来算法的正确性跟数学上的证明是有很大的关系的。不过对于我们来说，要验证一个算法对于所有输入的正确性是非常困难的，要通过严格的数学证明来解决。因此，应用中的算法以层次 3 为主。
===算法的可读性===
好算法的另外一个特征是可读性。
\\
\\
可读性：算法设计的另一个目的是为了方便别的程序员阅读。可读性有助于别人理解算法。
===算法的健壮性===
一个好的算法还应该对输入数据不合法的情况做适合的处理。
===时间、空间===
最后，好的算法还需要具备时间消耗少，空间占用少的特点。
\\
\\
算法的时间效率是指对于同一个问题，执行时间越少的算法效率越高。而空间占用则指算法运行时对存储空间的占用，占用越低系统资源消耗越少。
====算法效率的度量====
算法效率的估算大致分两种方法：
  * 事后统计
  * 事前估算
===事后统计===
都说实践出真知，对算法效率的测试，事后统计是一个很容易想到的办法：通过设计好的测试程序和数据，用计算机计时器对不同算法编制的程序的运行时间进行比较。但是这个办法存在很大的缺陷：
  * 依赖测试程序，耗费额外的精力。
  * 作为评判的标准之一时间受计算机软件、硬件的影响，可能会不精确。
  * 算法设计的测试数据很困难，而且往往对影响时间关系不大。
===事前估算===
事前估算的方法就是在计算机变之前，按照**统计方法对算法进行估算**。\\
\\
一个程序的时间效率取决于以下几点：
  * 算法采用的策略、方法。
  * 编译产生的代码的质量。
  * 问题的输入规模。
  * 机器执行指令的速度。
第二条取决于编译器，第四条取决于硬件。由此可以看出，算法对程序的影响主要体现在两方面：**算法的好坏**，**输入输出的规模**。\\
\\
算法的好坏直接体现在时间效率上，也就是运行多少次才能解决问题。而运行次数则跟输入输出的规模也有关系。因此我们我们在分析算法的时间的时候，需要把两个因素：**基本操作的数量**、**输入的规模**联系起来参考。我们来看看下图：
\\
\\
{{ :dsa:notes:dahua_ds:151255023901167.png?600 |}}
\\
有没有发现其实运行时间跟消耗的操作次数其实是正比关系？而且我们也可以看到，对于这些不同的算法来说，$n$ 越大，算法体现出来的差异就越明显。
====函数的渐进增长====
从书上的例子我们可以看到，只有当 $n$ 达到一定程度的时候，我们才能得知算法的优劣。因此，我们需要考察函数的**渐进增长效率**，也就是函数的自变量趋于无穷大的时候，算法的运行时间的增长。那么两个函数算法的优劣比较，其实也就为了算法时间增长率的比较。用数学定义来说就是：\\
\\
**给定两个函数$f(n)$、$g(n)$，存在一个整数$N$，使得对所有的 $n < N$，都有 $f(n) > g(n)$，那么我们称 $f(n)$的<wrap em>增长渐进</wrap>快于$g(n)$，也就是$f(n)$的时间效率优于$g(n)$。
**
\\
\\
而我们也可以发现，随着 $n$ 逐渐增大，算法中低次项的影响也越来越小（参考书上表格 //2-8-2，2-8-3//）。因此，当 $n$ 足够大的时候，无论是低次项，还是最高此项的前面的常数，都会越来越不重要。反过来，对于最高此项，伴随着$n$的增长，其结果也增长的非常快。因此我们可以看出来**函数的最高次项是算法时间效率的主要评判标准**。我们在之后的判定中也应该把注意力放在函数的最高次项上。
====算法的时间复杂度====
既然明白了算法的时间效率与什么有关，我们就可以用一个标记（notation）来表示算法的时间复杂度了。我们把用大写的 $O$ 来表示算法的复杂度，用 $T(n)$ 来表示算法语句执行的次数。因此我们可以给出算法复杂度的定义：\\
\\
**算法的时间复杂度记做 $T(n) = O(f(n))$。它表示随着问题规模 $n$ 的增大，算法执行的时间的增长率与函数本身相同。因此算法的时间复杂度也可以成为算法的渐进时间复杂度，简称时间复杂度。**
\\
===算法复杂度分析===
我们知道算法复杂度跟函数的最高次项是相关的。因此我们可以对函数做以下的处理：
  - 使用 ''1'' 取代所有的加法常数。
  - 只保留最高次项。
  - 如果最高次项存在，且不是 ''1'', 则去掉这个项想成的常数。
比如 $f(n) = 2n^2 + n + 1$ 的复杂度就是 $n^2$。
\\
具体的的分析主要查看的是数学的知识。不同的方式还有不同的求法，比如迭代用级数算，递归用递归方程算等，这本书比较浅，就不赘述了。
\\
\\
常见的时间复杂度有：
  * 常数阶：$O(1)$
  * 线性阶：$O(n)$
  * 对数阶：$O(logn)$
  * 平方阶：$O(n^2)$
  * 立方阶：$O(n^3)$
  * 指数阶：$O(2^n)$
===最坏、平均情况===
我们刚才说到的 $O$ 其实代表了算法的最坏时间复杂度，这是一种对算法性能的保证（最坏也就这样了）。而平均情况是很有意义的，因为它是期望的运行时间。不过现实中我们很难通过估算来计算平均复杂度，一般都是通过大量的数据来得出的。因此我们对算法复杂度的分析，默认指定的是最坏复杂度。
\\
\\
\\
----
~~DISQUS~~