20162330 2017-2018-1《程式設計與資料結構》第一周學習總結

2017-2018-1 學習總結目錄：　[**1**](http://www.cnblogs.com/super925/p/7499054.html)　[2](http://www.cnblogs.com/super925/p/7530927.html)　[3](http://www.cnblogs.com/super925/p/7586667.html)　[5](http://www.cnblogs.com/super925/p/7667978.html)　[6](http://www.cnblogs.com/super925/p/7667990.html)　[7](http://www.cnblogs.com/super925/p/7709745.html)　[9](http://www.cnblogs.com/super925/p/7787585.html)　[10](http://www.cnblogs.com/super925/p/7822055.html)　[11](http://www.cnblogs.com/super925/p/7859633.html)　[12](http://www.cnblogs.com/super925/p/8059078.html)

目錄

• 0. 教材學習内容總結

  * 0.1 算法效率

  * 0.2 增長函數和大O符号

  * 0.3 比較增長函數

• 1. 教材學習中的問題和解決過程

  * 1.1 指數階複雜度的計算

  * 1.2 線性語句序列

• 2. 代碼調試中的問題和解決過程

  * 2.1 根據程式語句分析頻度

  * 2.2 遞歸測試抛出異常StackOverflowError

• 3. 代碼托管、本周考試錯題總結

• 4. 結對及互評、其他（感悟、思考等，可選）

• 5. 學習進度條、參考資料

第12章 算法分析

教材學習内容總結

1.算法效率

• 計算：資訊處理的過程（借助某種工具）。
• 計算模型 = 計算機 = 資訊處理工具

• 算法：特定計算模型下為解決問題所使用的指令序列（輸入、輸出、正确性、确定性、可行性、有窮性）。

  【注】好算法最重要的是效率，要求速度盡可能快，存儲空間盡可能少。

• 資料結構：指互相之間存在一種或多種特定關系的資料元素的集合。資料結構三要素為 邏輯結構、存儲結構 和 運算 ，邏輯結構分為集合、線性、樹、圖，存儲結構分為順序、鍊式存儲等，運算建立在前兩個要素之上。

  

• Algorithms + Data Structures = Programs （N.Wirth,1976）

  (Algorithms + Data Structures) x Efficiency = Computation

• 算法效率的度量：算法效率主要由算法運作時間展現，算法運作時間等價于算法中每條語句執行時間之和，而每條語句執行時間又取決于每條語句的執行次數，是以可以把 語句頻度 和 漸進時間複雜度 作為算法效率的度量機關。（RAM）
• 算法效率的情形：最好效率、最差效率、平均效率。大量實踐經驗告訴我們，我們評價一個算法應該重點考慮 最差效率 這一點。舉個例子：

  

2.增長函數和大O符号

• 增長函數：顯示了與問題大小（n）相關的時間或空間使用率。
• 語句頻度：問題的規模為n時某個算法中的語句執行次數，記為 T(n)。
• 時間複雜度：某個算法的語句執行次數 f(n) 的上限，即此算法的漸進時間複雜度（簡稱時間複雜度) 或執行時間，記為 O(f(n))。一個分析時間複雜度的例子：

• 序号 | 程式語句 | 頻度f(n)與規模n|時間複雜度O(f(n))

  :---😐:---😐:---😐:---:

  1 |

  x=x+1; y=x+2

  | f(n) = 2 | O(1)

  2 |

  for(i=0;i<n;i++) x++;

  | f(n) = 2n+1 | O(n)

  3 |

  for(i=0;i<n;i++) for(j=0;j<n;j++) x++;

  | f(n) = (n+1)+n*(n+1)+\(n^2\) | O(\(n^2\))

  4 |

  i=1; while(i<=n) i=i*2;

  | \(2^{f(n)}\) = n | O(log\(_2\)n)

• 算法的階：漸進複雜度稱為算法的 階 ，表示階的記号稱為 O（） 或 Big-Oh 。

  【注】算法的階由算法增長的主項決定。一般情況下，階相同的算法在效率上等價。

• 漸進表示法記号 | 定義 | 含義

  :---😐:---😐:---:

  O |  f(n)＝O(g(n))，當 n ≥ n0 時，f(n) ≤ c·g(n)  |  f(n)的漸進上限為g(n) 

  Ω |  f(n)＝Ω(g(n))，當 n ≥ n0 時，f(n) ≥ c·g(n)  |  f(n)的漸進下限為g(n) 

  Θ |  f(n)＝Θ(g(n))，當 n ≥ n0 時，c\(_1\)·g(n) ≤ f(n) ≤ c\(_2\)·g(n)  |  f(n)的漸進确界為g(n) 

3.比較增長函數

• 

  【注】c < log\(_2\)n < n < nlog\(_2\)n < \(n^2\) < \(n^3\) < 2n < 3n < n!

  處理器速度的提升不能彌補算法的低效率。

【傳回目錄】

教材學習中的問題和解決過程

• 【問題1】我看了書中的第294頁比較增長函數标題下的内容，對照圖表，發現當問題大小為指數階的A4時，速度提升了3.3（即原問題的大小加3），但是按照前3個算法的提升規律，當處理器速度提升10倍時的效果，算法A1改善了10倍，A2改善了根号10倍，A3改善了10的立方根倍，是以我覺得當時間複雜度是\(n^4\)時，提升倍數應該是10的四次方根，而書中表格内容直接加上了3.3，即 log$_2$10 ，而且書中的文字是指數階複雜度，表格上A4算法就變成了幂階時間複雜度，實在想不通。

  

• 解決方案 ：詢問王志強老師，之後得出正确結論：算法A4的時間複雜度應該為\(2^n\)，是中文版教材上有問題，這樣一來就符合其速度提升的增長了。後來我也查詢了英文版教材，發現在英文第三版教材中是正确的，此問題到此為止。

  

• 【問題2】教材中提到“如果語句序列是線性的，則不管跳過什麼樣的語句，它的階仍是O(n)”。不太了解什麼是“線性”。之前學過“線性代數”，其中的“線性方程組”是指涉及數乘、加法的方程組，可是我依然不了解“線性”的含義。
• 解決方案 ：查詢之後了解到線性在這裡可以簡單地認為是一階導數為常數的函數，“線性”就是指量與量之間按比例、成直線的關系。在Android開發中LinearLayout控件也有應用。

代碼調試中的問題和解決過程

• 【問題1】：在根據程式語句分析頻度 f(n) 時，想不通為什麼第二層for的嵌套中頻度為n(n+1)，我的了解是将n作為這層語句的頻度，n+1作為上層語句的頻度，但是上層能傳入内層的頻度隻有n，緊接着，按這個思路分析，第三層的頻度也無法了解。

  

• 解決方案 ：詢問王志強老師，之後發現我的思路從第二層開始就錯了，第一層的n+1我能了解，但是我直接将第二層的n+1當成第一層傳入的頻度了，于是怎麼都想不通。第一層傳入的頻度應該是n，而第二層在每次第一層傳入時，都會增加n次頻度，加上每次臨界還要判斷一次，是以一共是n*(n+1)次，第三層以此類推也能了解了，這也正是針對嵌套循環的乘法準則。原來我一直認為n+1是第一層的，現在看來還是當時被自己的思路繞暈了，換種思路便豁然開朗。
• 【問題2】：在利用遞歸測試頻度很高時的程式時，抛出異常StackOverflowError，我不太了解為什麼相對其他簡單算法，遞歸算法的容納量（能夠執行的次數）相對較少。

  

• 解決方案 ：我原來隻想要設計一個簡單的遞歸來與其他算法比較，僅僅是一個累加相對于其他算法就少了那麼多運算範圍：

public static int getSum(int n){
            if(n==1){
                return 1;
            }else{
                return n+getSum(n-1);
            }
        }
           

查詢了相關資料之後，我了解到一些理論解釋：首先遞歸函數每次遞歸時都會調用一次本身的函數。函數調用的參數是通過棧空間來傳遞的，在調用過程中會占用線程的棧資源。而遞歸調用，隻有走到最後的結束點後函數才能依次退出，而未到達最後的結束點之前，占用的棧空間一直沒有釋放，如果遞歸調用次數過多，就可能導緻占用的棧資源超過線程的最大值，進而導緻棧溢出，導緻程式的異常退出。是以遞歸函數雖然較少代碼量，但是會消耗大量資源，非必要的時候不要使用遞歸。這一點在我的假期部落格中也有總結，當時的了解比較膚淺，現在終于驗證了一次。

• 順便記錄一下我對一個簡單的問題使用不同算法的比較結果，我發現好的數學模型對于算法效率很重要，計算1到n的和的簡單執行個體中，如果直接利用公式結論會比循環塊很多，尤其對于項數較多的情況。雖然遞歸也比循環快，但是範圍有限，資源有限，是以相比起來簡潔的數學模型更勝一籌。以下是運作時間的簡單測試：

  循環與遞歸的比較：（上：循環；下：遞歸）

  

  

  循環與數學公式的比較：（上：循環；下：公式）

  

  

代碼托管

• 本周代碼上傳至ch11和ch12兩個檔案夾裡：

  

  （statistics.sh腳本的運作結果截圖）

  

本周考試錯題總結

• 【錯題1】Determine the order of the following pseudocode fragment.

for j = 1 to n
 if (a > b) then
  for i = 1 to n
   print i
  next i
 else
  for i = 1 to 10
    print i
  next i
 end if
next j
           

A .O(1)

B .O(log n)

C .O(n)

D .O(n2)

E .O(2n)

F .None of the above

• 錯誤原因：沒有考慮到時間複雜度的情形，錯選C。

  加深了解：這段代碼片段最差的時間複雜度是O(n2)。在最好的情況下，它是O(n)。在不了解a和b的情況下，不可能找到平均情況的時間複雜度，除非另有說明，算法的階是指它最差的時間複雜度。是以我們評價一個算法也應該重點考慮 最差時間複雜度 這一點。

• 【錯題2】Determine the order of the following pseudocode fragment.

for i = 1 to 2*n
 print i
 print a
 print n
next i
           

• 錯誤原因：對算法的階了解有誤，認為這個循環執行了2n次階就是2n，錯選E。

  加深了解：這個循環将被執行2n次。但是當用大O符号表示算法的階時，常量就被忽略了。

• 【錯題3】Suppose Computer Program A implements an algorithm of order O(n). Suppose Computer Program B implements an algorithm of order O(n2). If the programs begin execution at the same time, we know that Computer Program A will complete execution first.

  A .true

  B .false

• 錯誤原因：沒有考慮一些客觀因素（輸入、頻度等），錯選A。

  加深了解：雖然計算機程式A被認為是“更快的”，但是我們不知道哪個程式會先完成，因為我們不知道輸入的大小或者與兩個算法的運作時間相關聯的常量。

結對及互評

• 莫禮鐘是我新的結對夥伴，他在學習上不是很主動，需要督促，我會适度監督他，盡可能讓他恢複一些學習的動力。本周他的狀态比上學期好一些，看了雲班課的幾個視訊也做了筆記，希望他可以繼續保持。

本周結對學習情況

• 20162319
• 結對學習内容
  • 雲班課上的視訊
  • 圖靈機模型

其他（感悟、思考等，可選）

• 本周是開學的第一周，我的狀态良好，較穩定，本周主要以理論内容為主，代碼實踐内容較少，我針對簡單的累加做了不同算法的測試。對照着課本，也看了雲班課上的視訊，雖然有些迷茫，但是本周的大體内容已掌握，可以說本周的學習任務相對較少。我覺得婁老師在課堂上講得有些快，是以課下也用了一些時間消化。下周會繼續保持(•̀ᴗ•́)و

• 【附】教材及考試題中涉及到的英語：

  Chinese | English | Chinese | English

  增長函數 | growth function | 僞代碼 | pseudocode

  時間複雜度 | time complexity | （代碼）段 | fragment

  空間複雜度 | space complexity | 記号 | notation

  漸進複雜度 | asymptotic complexity | 算法 | algorithm

  主項 | dominant term | 十倍（的） | tenfold

  （算法的）階 | order | 實作（執行） | implement

  常量 | constant | 子句 | clause

  數量級 | order(s) of magnitude | 插圖 | illustration

學習進度條

• | | 代碼行數（新增/累積）| 部落格量（新增/累積）|學習時間（新增/累積）|重要成長|

  | -------- | :----------------😐:----------------😐:---------------: |:-----😐

  | 目标 | 5000行 | 30篇 | 400小時 | |

  | 第一周 | 234/234 | 1/28 | 14/14 | 了解算法效率、大O符号等理論内容 |

• 計劃學習時間：15小時
• 實際學習時間：14小時
• 有效學習時間：5小時
• 改進情況：第一周效率相對較高，要保持好狀态，提高課堂效率。還是那句話：保持較低的動力，每天進步一點點。

參考資料

• 《Java程式設計與資料結構教程（第二版）》
• 《Java程式設計與資料結構教程（第二版）》學習指導
• 遞歸調用過多導緻的棧溢出問題說明
• 算法系列：算法效率分析
• 線性_360百科
• 第1章（緒論）