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

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

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

1）<b>输入</b>：有 0 个以上的输入                               2）<b>输出：</b>至少有 1 个输出

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

5）可行性：

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

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

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

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

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

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

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

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

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

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

答：1. T(n)= O(f(n))：若存在c &gt; 0，和正整数n0≥1，使得当n≥n0时， 总有 T(n)≤c*f(n)。 （给出了算法时间复杂度的上界，不可能比c*f(n)更大）

       2. T(n)=Ω(f(n))：若存在c &gt; 0，和正整数n0≥1，使得当n≥n0时， 存在无穷多个n ，使得T(n)≥c*f(n)成立。（给出了算法时间复杂度的下界，复杂度不可能比c*f(n)更小）

       3. T(n)= Θ(f(n))：若存在c1,c2&gt;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，各种增长函数的含义。

         答：

<b>数学表达式</b>

<b></b>

<b>相对增长率</b>

<b>T(N)=O(g(N))</b>

T(N)的增长 ≤ g(N)的增长

<b>T(N)=</b><b>Ω(g(N))</b>

T(N)的增长 ≥ g(N)的增长

<b>T(N)=</b><b>θ(g(N))</b>

T(N)的增长 ＝ g(N)的增长

<b>T(N)=</b><b>o(g(N))</b>

T(N)的增长 ＜ g(N)的增长

O(1)&lt;O(logn)&lt;O(n)&lt;O(nlogn)&lt;O(n2)&lt;O(n3)&lt;O(an)&lt;O(n!)&lt;O(nn)。

例题：

1，

<a href="http://blog.51cto.com/attachment/201203/012306740.png" target="_blank"></a>

2，

<a href="http://blog.51cto.com/attachment/201203/012402511.png" target="_blank"></a>

3，

<a href="http://blog.51cto.com/attachment/201203/012446694.png" target="_blank"></a>

4，

<a href="http://blog.51cto.com/attachment/201203/012602307.png" target="_blank"></a>

5，

<a href="http://blog.51cto.com/attachment/201203/012631777.png" target="_blank"></a>

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

答：O(n2)

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

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

 1000N            S1                    10S1

  10N2            S2                   3.16S2

   2N             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