什么是算法

所谓算法，是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列,还需要具备以下要素

• 输入与输出
• 基本操作与可行性
• 有穷性和正确性

不难理解，任意算法都应在执行有限次基本操作之后终止并给出输出，此即所谓算法的有穷
性（finiteness） 。进一步地，算法不仅应该迟早会终止，而且所给的输出还应该能够符合由
问题本身在事先确定的条件，此即所谓算法的正确性（correctness）

• 重用性

  计算效率

  首先需要确立一种尺度，用以从时间和空间等方面度量算法的计算成本，进而依此尺度对不同算法进行比较和评判。当然，更重要的是研究和归纳算法设计与实现过程中的一般性规律与技巧，以编写出效率更高、能够处理更大规模数据的程序。

  数据结构

  数据结构这一学科正是以“数据” 这一信息的表现形式为研究对象，旨在建立支持高效算法的数据信息处理策略、技巧与方法。要做到根据实际应用需求自如地设计、实现和选用适当的数据结构，必须首先对算法设计的技巧以及相应数据结构的特性了然于心。

  复杂度度量

  时间复杂度

  问题实例的规模往往是决定计算成本的主要因素，随着输入规模的扩大，算法的执行时间将如何增长，执行时间的这一变化趋势可描述为舒服规模的一个函数，称为该算法的时间复杂度(time complexity) 。从保守估计的角度出发，在规模为n的所有输入中选择执行时间最长者作为T(n)， 并以T(n)度量该算法的时间复杂度。

  渐进复杂度

  对于某些问题，一些算法更适合小规模输入，而另一些则相反。
  在评价算法运行效率时，我们往往可以忽略其处理小规模问题时的能力差异，转而关注其在处理更大规模问题时的表现。这种着眼长远、更为注重时间复杂度的总体变化趋势和增长速度的策略与方法，即所谓的渐进分析。

  基本操作

  一种自然且可行的解决办法是，将时间复杂度理解为算法中各条指令的执行时间之和。指令语句均可分解为若干次基本操作，比如算术运算、比较、分支、子程序调用与返回等；如此，不妨将T(n)定义为算法所执行基本操作的总次数。也就是说，T(n)决定于组成算法的所有语句各自的执行次数，以及其中所含基本操作的数目。

  大O记号法

  若存在正的常数c和函数f(n),使得对于任何n>>2都有 T(n) <= c.f(n),则可认为在n足够大后，f(n)给出了T(n)增长速度的渐进上界（算法的复杂度最坏情况）。此时记为: T(n) = O(f(n))

  • 对于任一常数c > 0，有O(f(n)) = O(c∙f(n))
  • 对于任意常数a > b > 0，有O(na + nb) = O(na)

前一性质意味着，在大O记号的意义下，函数各项正的常系数可以忽略并等同于1。后一性
质则意味着，多项式中的低次项均可忽略，只需保留最高次项。

大记号法

若存在正的常数c和函数g(n),使得对于任何n>>2都有 T(n) >= c.g(n),则可认为在n足够大后，g(n)给出了T(n)增长速度的渐进下界（算法的复杂度最好情况）。此时记为: T(n) = (g(n))

大记号法

从渐进的趋势看， T(n)介于 (g(n))与O(f(n))之间。若恰巧出现g(n) = f(n)的情况，则可以使用另一记号来表示。
如果存在正的常数c1 < c2和函数h(n)，使得对于任何n >> 2都有c1∙h(n)<=T(n)<=c2∙h(n),就可以认为在n足够大之后,h(n)给出了T(n)的一个确界。
T(n) = (h(n))

空间复杂度

算法所需存储空间的多少。很多时候我们都是更多地甚至仅仅关注于算法的时间复杂度， 而不必对空间复杂度做 专门的考查。

复杂度分析

常数

T(n) = O(1)
一般地， 仅含一次或常数次基本操作的算法均属此类。此类算法 通常不含循环、分支、子程序调用等。

对数

由大O记号定义，在用函数logrn界定渐进复杂度时，常底数r的具体取值无所谓故通常不予专门标出而笼统地记作logn。比如，尽管此处底数为常数2，却可直接记 作O(logn)。此类算法称作具有“对数时间复杂度”
对数的运算法则

1、log(a) (M·N）=log(a) M+log(a) N
2、log(a) (M÷N)=log(a) M-log(a) N
3、log(a) M^n=nlog(a) M
4、log(a)b*log(b)a=1
5、log(a) b=log (c) b÷log (c) a

线性

凡运行时间可以表示和度量为T(n) = O(n)形式的这一类算法， 均统称作“线性时间复杂 度算法”

多项式

若运行时间可以表示和度量为T(n) = O(f(n))的形式，而且f(x)为多项式，则对应的算法 称作“多项式时间复杂度算法” 。从理论上讲， 复杂度分别为O() 和O()算法都同属此类，尽管二者实际的计算效率有天壤之别

指数

一般地， 凡运行时间可以表示和度量为T(n) = O()形式的算法（a > 1），均属于“指 数时间复杂度算法” （exponential-time algorithm）

复杂度层次

输入规模