算法設計與分析複習——第一章：算法引論

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