算法概念
有限条操作指令的集合,确定了解决问题的方法和步骤。能够对符合一定规范的输入,在有限时间内获得所要求的输出
- 欧几里算法
m = q*n + r
算法特征
- 确定性
- 多样性
- 有穷性
- 输入、输出
程序是算法的一种表达和实现形式,程序可以不具备有穷性。
算法表述:
- 伪代码
- 流程图
算法的计算复杂度
定义(平均复杂度):
对给定的算法A,如何评估其平均复杂度?
设 Dn 为 A 的输入集,其中 n 为 A 的输入规模,I ∈ Dn 即 I 为其中的一个输入类,P(I) 为 I 出现的概率,t(I) 为 I 对应的基本操作数,则 A(n) = ∑I ∈ Dn P(I) * t(I)。
最坏复杂度:W(n) = max I ∈ Dn { t ( Ii ) }
最佳复杂度:B(n) = min I ∈ Dn { t ( Ii ) }
最后:B(n) <= A(n) <= W(n)
算法分析原则:
- 正确性
- 工作量-时间复杂度(最坏、平均)
给定问题该算法执行基本运算的次数 - 占用空间-空间复杂度(最坏、平均)
1.存储程序和输入数据空间 2.存储中间结果或操作单元所占用额外空间 - 简单性
- 最优性(最坏、平均)
分析框架
- 输入问题的规模
算法的时间效率和空间效率都用输入规模的函数进行度量。 - 运行时间的度量单位
把基本操作(最重要操作)次数作为算法运行时间的度量单位 - 增长次数
- 最优、最差和平均效率
在输入规模相同的情况下,有些算法的效率会的显著差异。对于这样的算法,我们需要区分最差效率,平均效率和最优效率。
本框架主要关心,当算法的输入规模趋向于无限大的时候,其运行时间(消耗的额外空间)函数的增长次数。
渐近符号和基本效率类型
渐进符号和基本效率类型复杂度函数的阶.png- 利用极限比较增长次数 极限比较增长次数.png
前两种情况意味着 f (n) ∈ O (g(n)) ,后两种情况意味着 f (n) ∈ Ω (g(n)) ,第二种情况意味着 t (n) ∈ Θ (g(n))。
基本效率类型
大小.PNG非递归算法的时间复杂度分析
- 基本步骤:
1.确定算法的输入规模;
2.确定算法的基本操作(作为一种规律,它总是位于算法的最内层循环中);
3.检查基本操作的执行次数是否只依赖输入规模,对应的最坏、最佳情况;
4.建立一个算法基本操作执行次数的求和表达式;
5.利用求和运算导出复杂度,至少确定它的量级(增长次数)。
分析递归算法效率的基本步骤
1.确定用哪个(哪些)参数作为输入规模的度量;
2.找出算法的基本操作;
3.检查一下,对于相同规模的不同输入,基本操作的执行次数是否不同。如果不同,则必须对最差效率、平均效率及最优效率作单独研究;
4.对于算法基本操作的执行次数,建立一个递推关系以及相应的初始条件;
5.解递推式,或至少确定它的有解的增长次数。
算法设计
例:在n个元素的集合S中找出最大元素
一、算法思想
1.将S中的元素两两分组,每组生成较大元素,将较小元素从S中去掉(标记)
2.在当前S上重复步骤1的工作直到仅剩一个元素
二、形式化描述(伪代码略)
三、复杂度分析(归纳法)
分析:要证此类二叉树内点个数为n-1 (设叶结点个数为n)
1.当n=1,不花费比较,结论成立;
2.当n=2,花一次比较,内点个数为1,结论成立;
3.设n<=k时,结论成立
当n=k+1时,不妨设左子树叶子结点数为 l ,右子树叶子结点数为 r ,则 l + r = k + 1,并且 1 <= l <= k , 1 <= r <= k,则左子树的内点数为 l - 1,右子树的内点数为 r - 1,整个树的内点数为 ( l-1 ) +( r-1 ) + 1 = l + r - 1 = k
由归纳法原理,对于任意 n ,结论均成立。
网友评论