《算法设计与分析》,计算理论与算法分析设计

　　算法及其重要特征算法：对解决一个特定问题的步骤的描述，是一个有限的指令序列。

　　算法的五个特征：

　　(1)输入：一个算法有零个或多个输入。

　　输出：一个算法有一个或多个输出。

　　有限性：一个算法在执行有限个步骤后总要结束，每个步骤都在有限时间内完成。

　　确定性：算法中的每一条指令都必须有确切的含义，同样的输入只能得到同样的输出。

　　5]可行性：算法所描述的运算可以通过执行已经实现了有限次的基本运算来实现。

　　问题解决流程：

　　分析问题设计算法写程序整理结果。

　　算法：对解决特定问题的步骤的描述，它是一个有限的指令序列。

　　例如：欧几里德的算法3354，相间除法，求两个自然数M和n的最大公约数。

　　算法设计的一般过程

　　1.理解问题

　　2.预测所有可能的输入

　　3.在精确解和近似解之间选择。

　　4.确定适当的数据结构

　　5.算法设计技术。

　　6.描述算法

　　7.跟踪算法

　　8.分析算法的效率

　　9.根据算法写代码

　　算法分析

　　算法分析：估算算法需要的两种计算机资源——小时和空间。

　　时间复杂度(时间复杂度)

　　空间复杂性(空间复杂性)

　　分析的目的：

　　设计算法——设计一个复杂度尽可能低的算法。

　　选择算法——在各种算法中选择复杂度最低的算法。

　　时间复杂性分析的关键：

　　问题的规模：投入的多少；

　　基本语句：整个算法的执行次数和执行时间。

　　比例陈述

　　渐进符号

　　大o符号

　　1.1若有两个正常数c和n0，且对任意nn0，有T(n)cf(n)，则T(n)=O(f(n))，或算法在O(f(n)中。大符号

　　1.2若有两个正常数c和n0，且对任意nn0，有T(n)cg(n)，则称为t (n)= (g (n)) 符号。

　　1.3若有三个正常数c1、c2、n0，且对任意nn0，c1f(n)T(n)c2f(n)，称为t (n)= (f (n)的最好、最差、平均情况。

　　结论：如果问题规模相同，时间成本与输入数据相关，则需要分析最佳情况、最差情况和一般情况。

　　最好的情况：发生概率高的时候分析。

　　最坏的情况：实时系统

　　一般情况：知道输入数据是如何分布的，

　　通常假设等概率分布。

　　非递归算法分析

　　决定用哪个(或哪些)参数作为算法问题规模的度量，找出算法中的基本语句，检查基本语句的执行次数是否只取决于问题的规模，建立基本语句执行次数的求和表达式，用递进符号表示这个求和表达式。

　　关键：建立一个表示算法运行时间的求和表达式，然后用渐近符号来表示这个求和表达式。

　　版权归作者所有：原创作品来自博主Kieary，转载授权请联系作者，否则将追究法律责任。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。