2017-2018-1 學習總結目錄：　1　2　3　5　6　7　9　10　11　12

目錄

• 0. 教材學習內容總結
  • 0.1 算法效率
  • 0.2 增長函數和大O符號
  • 0.3 比較增長函數

• 1. 教材學習中的問題和解決過程
  • 1.1 指數階復雜度的計算
  • 1.2 線性語句序列

• 2. 代碼調試中的問題和解決過程
  • 2.1 根據程序語句分析頻度
  • 2.2 遞歸測試拋出異常StackOverflowError

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

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

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

教材學習內容總結

1.算法效率

• 計算：信息處理的過程（借助某種工具）。

• 計算模型 = 計算機 = 信息處理工具

• 算法：特定計算模型下為解決問題所使用的指令序列（輸入、輸出、正確性、確定性、可行性、有窮性）。
  【注】好算法最重要的是效率，要求速度盡可能快，存儲空間盡可能少。

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

• Algorithms + Data Structures = Programs （N.Wirth,1976）
  (Algorithms + Data Structures) x Efficiency = Computation

• 算法效率的度量：算法效率主要由算法運行時間體現，算法運行時間等價于算法中每條語句執行時間之和，而每條語句執行時間又取決于每條語句的執行次數，所以可以把 語句頻度 和 漸進時間復雜度 作為算法效率的度量單位。（RAM）

• 算法效率的情形：最好效率、最差效率、平均效率。大量實踐經驗告訴我們，我們評價一個算法應該重點考慮 最差效率 這一點。舉個例子：
  

2.增長函數和大O符號

• 增長函數：顯示了與問題大?。╪）相關的時間或空間利用率。

• 語句頻度：問題的規模為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);
          }
      }
  

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

• 順便記錄一下我對一個簡單的問題使用不同算法的比較結果，我發現好的數學模型對于算法效率很重要，計算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

A .O(1)
B .O(log n)
C .O(n)
D .O(n2)
E .O(2n)
F .None of the above

• 錯誤原因：對算法的階理解有誤，認為這個循環執行了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

【返回目錄】

學習進度條

• 計劃學習時間：15小時

• 實際學習時間：14小時

• 有效學習時間：5小時

• 改進情況：第一周效率相對較高，要保持好狀態，提高課堂效率。還是那句話：保持較低的動力，每天進步一點點。

參考資料

• 《Java程序設計與數據結構教程（第二版）》

• 《Java程序設計與數據結構教程（第二版）》學習指導

• 遞歸調用過多導致的棧溢出問題說明

• 算法系列：算法效率分析

• 線性_360百科

• 第1章（緒論）

【返回目錄】