算法设计与分析笔记之(1)：算法概述

声明

1）本文仅供学术交流，非商用。具体引用的资料请看参考文献。如果某部分不小心侵犯了大家的利益，请联系博主删除。

2）本人才疏学浅，整理总结的时候难免出错，还望各位前辈不吝指正，谢谢。

联系方式：[email protected]

第一章  算法概述

第一节 用计算机求解问题与算法

1.计算机求解问题的步骤：

a)       问题分析

b)       数学模型建立

c)       算法设计与选择

d)       算法表示：图形、流程图、数学表达等

e)       算法分析：确定衡量算法的标准包括：精度、时间度和空间度

f)        程序调试

g)       结果整理和文档编制

2.算法定义：

在解决问题时，按照某种确定的步骤可以得到问题结果的处理过程。

3.算法的三要素：

a)       操作：加减乘除，与或非等运算

b)       控制结果：顺序结构、选择结构和循环结构

c)       数据结构：数据的存储方式和处理方式

4.算法的特征：

有穷性、确定性、可行性、有输入、有输出

5.算法设计必须严格考虑的质量指标

a)       正确性：对确定的输入有唯一的结果

b)       可读性：容易看懂

c)       健壮性：当有错误输入是能给出提示

d)      高效率与低存储量

6.算法设计的基本模型

结构化方法、面向兑现方法

7.算法实现的注意事项

a)       数据类型的选择

b)       计算过程的差异

c)       结果输出的格式

d)       算法实现后的测试和调试

第二节 算法描述

1.算法的描述方式：

a)       自然语言

b)       流程图

c)       盒图

d)       PAD图

e)       伪代码

f)        程序设计语言

2.常用算法分类

a)       压缩/解压算法

b)       加密/解密算法

c)       人工智能算法

d)       并行算法

e)       其他算法：数值算法、运筹学相关算法、统计学相关算法、网络搜索引擎算法

第三节 算法复杂性分析

1.算法分析的评价体系：

a)       算法实现的消耗时间T(N)

b)       算法实现占用的存储空间S(N)

c)       算法应易于理解和调试

2.算法时间效率的衡量方法

①事后分析法：实际测量算法的执行时间（不常用）

②事前分析估算法:主要通过算法复杂度来体现

3.时间复杂性

其中D_N是规模为N的合法输入的集合；I^*是D_N中使T(N,I^*)达到T_max(N)的合法输入；是中使T(N, )达到T_min(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。

4.时间复杂性的渐近

①渐近上界O的定义

如果存在正的常数C和自然数N0，使得当NN0时有f(N)=Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。

②渐近下界Ω的定义

如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。即f(N)的阶不低于g(N)的阶。 

③同阶Q的定义

定义f(N)=Q(g(N))当且仅当f(N)=O(g(N))且f(N)= Ω(g(N))，即(g(n))={f(n)|存在正常数c1,c2和正整数n0使得对所有n≥n0有：c1g(n)≤f(n)≤c2g(n)}，此时称f(N)与g(N)同阶

④低阶o的定义

对于任意给定的ε＞0，都存在正整数N0，使得当N³N0时有f(N)/Cg(N)ε,则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N))。

⑤非紧下界记号w

w(g(n))= { f(n) | 对于任何正常数c>0，存在正数和n₀ >0使得对所有n³n₀有：0 £ cg(n) < f(n) }。

5.算法分析中常见的复杂性函数

常见的复杂性函数

 

小规模数据

 

中等规模数据

  

6.算法分析案例

例：顺序搜索算法

程序：

template<class Type>

int seqSearch(Type *a, int n,Type k)

{

     for(int i=0;i<n;i++)

        if (a[i]==k) return i;

     return -1;

}

（1）T_max(n) = max{ T(I)| size(I)=n }=O(n)

（2）T_min(n) = min{ T(I)| size(I)=n }=O(1)

（3）在平均情况下，假设：

     

7.最优算法

问题的计算时间下界为W(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法。