算法复习参考

算法复习答案1. 什么是基本运算？答：基本运算是解决问题时占支配地位的运算（一般 1 种，间或两种）；讨论一个算法优劣时，只讨论基本运算的执行次数。2. 什么是算法的时间复杂性（度）？答：算法的时间复杂性（度）是指用输入规模的某个函数来表示算法的基本运算量。T(n)=4n33. 什么是算法的渐近时间复杂性？答：当输入规模趋向于极限情形时（相当大）的时间复杂性。4. 表示渐进时间复杂性的三个记号的具体定义是什么？ 答：1. T(n)= O(f(n))：若存在 c > 0 和正整数 n0≥1，使得当 n≥n0时， 总有 T(n)≤c*f(n)。 （给出了算法时间复杂度的上界，不可能比 c*f(n)更大） 2. T(n)=Ω(f(n))：若存在 c > 0 和正整数 n0≥1，使得当 n≥n0时， 存在无穷多个 n ，使得 T(n)≥c*f(n)成立。（给出了算法时间复杂度的下界，复杂度不可能比c*f(n)更小） 3. T(n)= Θ(f(n))：若存在 c1,c2>0，和正整数 n0≥1，使得当 n≥n0时， 总有 T(n)≤c1*f(n)，且有无穷多个 n，使得 T(n)≥c2*f(n)成立， 即：T(n)= O(f(n))与T(n)=Ω(f(n))都成立。（既给出了算法时间复杂度的上界，也给出了下界）5. 什么是最坏情况时间复杂性？什么是平均情况时间复杂性？答：最坏情况时间复杂性是规模为 n 的所有输入中，基本运算执行次数为最多的那个输入的时间复杂性。 平均情况时间复杂性是规模为 n 的所有输入的算法时间复杂度的平均值 （一般均假设每种输入情况以等概率出现）。6. 一般认为什么是算法？什么是计算过程？答：一般认为，算法是由若干条指令组成的有穷序列，有五个特性1） 确定性：每条指令都是明确的、无二义的 2） 能行性：每条指令都必须是能够执行的 3） 输入：允许有 0 个或多个输入量，取自特定的集合。 4） 输出：产生一个或多个输出，它（们）与输入量之间存在着某种特定的关系。 5） 有穷性：每一条指令执行的次数都是有穷的。 只满足前 4 条而不满足第 5 条的有穷指令序列通常称之为计算过程。 7. 算法讨论有哪几个主要步骤？主要从哪几个方面评价算法？答：算法讨论的主要步骤：1） 设计：要根据不同的处理对象设计出高质量的算法。 2） 表示：如何能使得算法的表示简明扼要， 写出的算法要保证能在计算机上实现。 3） 确认：对所有合法的输入，所给算法都要能得到正确的结果；对所有不合法的输入，算法都要能够正确应对。 4） 分析：估计算法能在什么样的环境中有效地...