数据结构与算法(一)

算法是指基于特定的算法模型,旨在解决某一信息处理问题而设计的一个指令序列。

算法应具备几个要素:

  • 输入与输出:对所求问题特定实例的描述称为输入(input),经计算和处理之后得到的 信息,即针对输入问题实例的答案,称为输出(output)。在物理上,输出有可能存放 于单独的空间,也可能直接存放在原输入所占的存储空间。
  • 基本操作、确定性与可行性:所谓的确定性和可行性是说算法应可描述为由若干条语义 明确的基本操作组成的指令序列,且每一基本操作在对应的计算模型中均可实现。
  • 有穷性与正确性: 有穷性(finiteness)是指算法应在执行有限次操作后给出输出。进 一步讲,算法不仅会停止,而且输出应符合由问题本身在事先确定的条件,即正确性。
  • 退化与鲁棒性: 指的是算法的健壮程度,即需要处理各种极端的输入实例,这种极端 情况就是退化。而鲁棒性就是能充分的应对此类情况。
  • 重用性: 即算法的框架能否便捷的推广到其他场合,多适用性。

算法效率

当我们在谈论一个算法时,如何评价这是一个好算法还是一般的算法。

  1. 可计算性可计算性是指当编写的代码没有语法错误能顺利编译的情况下,在执行过程中 却会出现栈溢出或者无限递归的问题,更甚者,有些应用问题就无法设计出终止的算法 。
  2. 难解性与计算效率算法对任何输入都能在有穷次操作后输出,然而我们必须要关注的是 这其中需要的时间,并需要尽量压缩时间和空间成本。
  3. 数据结构无论是算法的输入、输出还是中间计算过程,在计算机中都始终以数据的形式 而存在。对于数据的存储、组织、转移等操作,不同的计算模型和平台环境所支持的具 体形式不尽相同,其执行效率直接影响算法的效率。这就是数据结构的意义所在。

复杂度度量

时间复杂度

首先必须明白的是,运行时间由多种因素综合作用而决定。在诸多因素里问题实例的规 模往往是决定计算成本的主要因素。一般地,问题规模越大,所需时间越多。随着输入 规模的扩大,算法的执行时间将如何增长? 执行时间的这一变化趋势可表示为输入规模 的一个函数,称作该算法的时间复杂度(time complexity).具体地,特定算法处理规模为 n 的问题所需的时间记为$T(n)$.从保守估计的角度出发,在规模为 n 的所有输入中执行 时间最长者为$T(n)$,以$T(n)$来度量该算法的时间复杂度。

渐进复杂度

至此,比较同一问题的两个算法 A 和 B,通过比较其时间复杂度$T_A(n)$和$T_B(n)$,即 可评价二者对于同一规模 n 的计算效率高低。然而有些算法更适用于小规模的输入,在这 种情况下,时间成本就不是一个值得计较的东西,我们可以忽略其处理小规模问题的能力差 异,转而关注其在更大规模问题上的表现。

大 O 记号

探讨 T(n)的渐进上界,我们需引入"大 O 记号"。具体的,若存在正常数 c 和函数 f(n), 对于任何 n »2 都有
$T(n) ≤ c*f(n)$
则 n 足够大之后,f(n)给出 T(n)增长速 度的一个上界,此时记:
$T(n) = O(fn(n))$
由此得出大 O 记号的一下性质 :

  1. 对于任意常数 c>0,有
    $ O(f(n)) = O(c*f(n))$
  2. 对于任意常数 a>b>0,有
    $O(n^a + n^b) = O(n^a)$

环境差异、基本操作

在实际环境中测出的$T(n)$,无法完全准确的衡量一个算法。不同的硬件平台不同操作系统 都会影响时间。我们需要一种客观的超脱于具体硬件平台和系统等因素的标准来衡量。当把 时间复杂度理解为算法中各条指令的执行时间之和时,不妨将$T(n)$定义为算法所执行基本 操作的总次数。即$T(n)$决定于组成算法的所有语句各自的执行次数以及所含基本操作的数 目。

最好最坏平均情况

为了对算法复杂度最好的情况做出估计,需要用 Ω 来标记。
如果存在正的常数 c 和 函数 g(n),使得对于任何 n»2 都有:
$T(n) ≥ c*g(n)$
n 足够大时,g(n)给了 T(n)一个渐进下界,则:
$T(n) = Ω(g(n))$
这里的 Ω 叫做"大 Ω 记号",是算法 最好情况下的执行——对于规模为 n 的输入,算法的运行时间都不低于$Ω(g(n))$。

通过大 Ω 记号,大 O 记号可以对算法的时间复杂度做出定量的界定,从渐进的趋势来看 ,$T(n)$介于$Ω(g(n))$和$O(f(n))$之间,若出现$g(n)=f(n)$的情况,则用 Θ 来表示。若 存在正的常数$C_1 < C_2$,和函数 h(n),使得对于任意$n»2$都有:
$C_1●h(n) ≤ T(n) ≤ C_2●h(n) $
n足够大之后,h(n)给出了T(n)一个确界:
$T(n) = Θ(h(n))$