[Introduction To Algorithms] 第一堂: Getting Started (2)

延續上個問題

• 為什麼 c 和 cn 使用的是同樣的 c ?

書上的說法是 c 取上界，取下界算出來的答案都是 nlg n。

而到了 chapter 4 時有個理論可以說明即使都用 c 還是沒差 (印象中好像是 master theorem = =) 

老師補充了他自己的證明，不一樣的�nnlg�nn變常數變

就用不一樣的常數變數表示。這樣證明比較簡單，不用用三明治的方式上下夾擊。

接下來比較 insertion 和 merge sort 的係數。

因為 merge 需要漲堆疊、而且要 copy array 所以係數會比較高。因此若是 input size 很小時，insertion sort 會比較快。但是要小到甚麼程度呢?

這就要看執行環境了...

Note:

• 估算空間複雜度時，是估算額外用到的空間，原本的空間是本來就要用的。
• 所以排序要比較快，就是用混用的方法，一開始遞迴呼叫 merge sort 等到 input size 夠小時，呼叫 insertion sort

接下來講測量方法。老師用工作站來 demo gprof 的使用方式。

• -Dk 代表 #define k 

這裡用 shell script 來 filter 不需要的資訊

• A2 指的是保留兩列

就降!