算法设计与分析复习——第一章：算法引论

第一章：算法引论

1，什么是算法？算法有哪些基本特征？请指出算法同程序的相同点与不同点。

         答：算法是解决问题的方法或过程，是满足以下四个性质的指令序列

1）输入：有 0 个以上的输入                               2）输出：至少有 1 个输出

3）确定性：指令清晰、无歧义                            4）有限性：指令执行次数有限，时间有限

5）可行性：

        算法和程序的相同点：两者都具有输入、输出和确定性的特征 不同点：程序是算法用某种程序语言的具体实现，程序不满足算法具有的有限性性质 请描述算法设计的一般过程。

2，请描述算法设计的一般过程。

答：算法设计的一般过程是 1）提出问题 2）确定数学模型 3）明确目的、条件和约束关系 4）设计求解步骤 5）结果评估与分析 如果在第 5 步的分析中对算法时间、空间复杂度或结果不满意，可以返回第 1 步或第 4 步进一步迭代，直至找到满意的算法。

3，什么是算法复杂性？它主要有哪两个方面构成？

         答：算法复杂性是算法运行时所需要的计算机资源的量，它包括两个方面：时间复杂性（需 要时间资源的量）和空间复杂性（需要空间资源的量） 。

4，时间复杂性分析主要分哪三种情况，哪种情况的可操作性最好，最具有实际价值？

         答：时间复杂性分为 3 种情况，最好情况、平均情况、最坏情况，可操作性最好，最具有实 际价值的是最坏情况下的时间复杂性。

         最坏情况时间复杂性是规模为n的所有输入中，基本运算执行次数为最多的时间复杂性。

   平均情况时间复杂性是规模为n的所有输入的算法时间复杂度的平均值 （一般均假设每种输入情况以等概率出现）。

5，表示渐进时间复杂性的三个记号的具体定义是什么？

答：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))都成立。（既给出了算法时间复杂度的上界，也给出了下界）。

6，算法研究有哪几个主要步骤？主要从哪几个方面评价算法？

答：算法研究的主要步骤是1)设计2）表示 3）确认，合法输入和不合法输入的处理 4）分析 5）测试。

评价算法的标准有1）正确性 2）健壮性 3）简单性 4）高效性 5）最优性

7，各种增长函数的含义。

         答：

O(1)<O(log_n)<O(n)<O(nlog_n)<O(n²)<O(n³)<O(aⁿ)<O(n!)<O(nⁿ)。

例题：

1，

2，

3，

4，

5，

6，如果算法A由三个步骤组成，其中第一步的时间复杂性为O(n²)，第二步的时间复杂性为O(nlogn)，第三步的时间复杂性为O(n)，请问算法A的时间复杂性是多少？

答：O(n²)

7, 解决某问题有三种算法，复杂性分别为1000N，10N2， 2N ，在一台机器上可处理问题的规模分别为S1 ， S2 ， S3 。若机器速度提高到原来的10倍，问在同样时间内可处理问题的大小如何？

         答：

复杂性       原来处理问题规模      速度提高以后    

 1000N            S1                    10S1

  10N²            S2                   3.16S2

   2^N             S3               S3 +log10≈ S3 +3.32

8，问题P的算法复杂度为T(n)=n3（毫秒），现改善为T(n)=n2（毫秒）。问原来运行一小时的问题实例，现在要运行多少时间？

答：

设实例大小为n，

        则 n3=3600*1000

        n=153.3

       ∴ 现在需要时间t=153.32毫秒≈ 23.5秒

9，

1），f(n) = 2n + 3 = O(n)

当n≥3时，2n+3≤3n，所以，可选c = 3，n0 = 3。对于n≥n0，f(n) = 2n + 3≤3n，所以，f(n) = O(n)，即2n + 3O(n)。这意味着，当n≥3时，程序2-1的程序步不会超过3n，2n + 3 = O(n)。

2），f(n) = 10n2 + 4n + 2 = O(n2)

对于n≥2时，有10n2 + 4n + 2≤10n2 + 5n，并且当n≥5时，5n≤n2，因此，可选c = 11, n0 = 5；对于n≥n0，f(n) = 10n2 + 4n + 2≤11n2，所以f(n) = O(n2)。

3），10n2 + 9  O(n)

使用反证法，假定存在c和n0，使得对于n≥n0，10n2 + 9≤cn始终成立，那么有10n + 9/n≤c，即n≤c/10  9/(10n)总成立。但此不等式不可能总成立，取n = c/10 + 1时，该不等式便不再成立。

本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/802712