DS之算法概述

算法 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有5个重要的特性。 (1)有穷性 一个算法必须总是(对任何合法的输入)在执行有穷步之后结束，且每一步都可在有穷时间内(合理的，可接受的

算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有5个重要的特性。

(1)有穷性 一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内(合理的，可接受的时间内)完成。

(2)确定性 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。

(3)可行性 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

(4)输入 一个算法有零个或多个的输入，这些输入取自某个特定的对象集合。

(5)输出 一个算法有一个或多个的输出，这些输出是同输入有某些特定关系的量。

算法设计的要求

(1)正确性 算法应当满足具体问题的需求。

(2)可读性 算法主要是为了人的阅读和交流，其次才是机器执行。可读性有助于人对算法的理解。

(3)健壮性 当输入数据非法时，算法也能适当地做出反应或进行处理，不会产生莫名其妙的输出结果。

(4)效率与低存储量需求 通俗地说，效率指的是算法执行的时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。效率与低存储量需求都与问题规模有关。

算法效率的度量

算法执行时间需要通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法：

(1)事后统计的方法

(2)事前分析估算的方法

一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

1，依据的算法选何种策略

2，问题的规模

3，书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越低。

4，编译程序所产生的机器代码的质量

5，机器执行指令的速度

一个算法是由控制结构(顺序，分支和循环三种)和原操作(指固有数据类型的操作)构成的，则算法时间取决于两者的总和效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。

算法的时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n)),它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。

显然，被称作问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。

下面通过几个例子来说明时间复杂度

1，{ ++x; s=0; } “x增1”的语句的频度为1，则时间复杂度为O(1)常量阶

2，for(int i=1; i<=n; i++) { ++x; s+=x; } “x增1”的语句的频度为n，则时间复杂度为O(n)线性阶

3，for(int i=1; i<=n; i++)

for(int j=1; j<=n; j++) { ++x; s+=x; } “x增1”的语句的频度为n*n，则时间复杂度为O(n*n)平方阶

算法还可能呈现的时间复杂度有对数阶，指数阶等【本文来自鸿网互联 (http://www.68idc.cn)】。

算法的存储空间需求

类似于算法的时间复杂度，而空间复杂度作为算法所需要存储空间的量度，记作S(n)=O(f(n)),其中n为问题的规模(或大小)。一个上机执行的程序除了需要存储空间来寄存本身所用指令，常数，变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需要信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间，否则应同时考虑输入本身所需要空间(和输入数据的表示形式有关)。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。

如果所占空间量依赖于特定的输入，则除特定指明外，均按最坏情况来分析。