1-算法与复杂性分析

《1-算法与复杂性分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机算法设计与分析算法与复杂性分析姜大志汕头大学计算机系算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性（有穷性）：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。(5)可行性：算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成；（也称之为有效性）22021/7/29程序(Program)程序是算法用某种程序设计语言的

2、具体实现。程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。2021/7/293问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法2021/7/294构建模型模型的构建是理解问题的结果；模型：是对实体的特征及变化规律的一种表示或抽象，即是把对象实体通过适当的过滤，用适当的表现规则描绘出的简洁的模仿品。2021/7/295模型的分类（1）实体

3、模型1、模拟模型2、事物模型（2）符号模型1、数学模型2、结构模型3、模仿模型4、科学符号5、描述模型理解问题和模型构建是问题求解的关键！关于均值2/3的猜想在这个游戏中，要求所有参与者在不知道其他人选择的情况下，每人给出一个0到100之间的数字，所给出的数字最接近平均值2/3的那个人将会是获胜者。2021/7/296你将如何获胜？模型的构建1按照理性人的假设，参与者们应该会先排除不可能的数字。例如超过67的数字就不可能，因为当大家都选100时，平均值的三分之二才不过66。这样一来，每个人的选择又变成了在0到66之间选一个数，此时大于44的数字又变得没有意义了，接下来又

4、是一个类似的循环……直到最后，所有理性人的选择应该都为0。但是我相信在座并不是所有参与者都会遵照理性人的思路来思考这个问题，我假设有三分之一的人是任意的给出一数字，那么这三分之一人的均值的三分之二应该接近33，另外三分之一的人我们假定是进行这理性推理，选择的均值为0，最后三分之一我们我们考虑到存在一群和我有一样思维模式的人，认为一部分人理性一部分人不理性，那么他会选择两者均值的2/3，所以他会取值11，在对这三种人的均值的猜想下求均值的2/3,得到我的猜想为10.2021/7/297模型的构建2首先采用二八定律进行人群的划分，假设80%的人会在0到100之间随机选择一个数，

5、那么可得80%的均值的2/3为33。还有20%的人是极度理性的人，他们选择平均数将在33左右间选择，设定为28~38，这种人在28到38之间随机选择一个数。通过计算模拟后得出总体均值的2/3为31左右。程序见附件。2021/7/298反思一个模型到底有多重要？模型中最重要的组成部分是什么？你还能够构建哪些模型？2021/7/299算法复杂性分析算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。2021/7/2910算法的时间复杂性（1）最坏情况下的时间复杂性Tmax(n)=max{T(I)

6、size(I)=

7、n}（2）最好情况下的时间复杂性Tmin(n)=min{T(I)

8、size(I)=n}（3）平均情况下的时间复杂性Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。2021/7/2911算法渐近复杂性T(n),asn;(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。2021/7/2912渐近分析的记号在下面的讨论中，对所有n，f(n)0，g(n)0。（1）渐近上界记号OO(g(n))={f(n)

9、

10、存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}（2）渐近下界记号(g(n))={f(n)

11、存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}2021/7/2913（3）非紧上界记号oo(g(n))={f(n)

12、对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0f(n)

13、对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0cg(n)