[Introduction To Algorithms] 第二堂: Growth of Functions

   老師講了一個觀念我覺得很不錯，Asympotic 也就是漸進線的意思，當 n 夠大時，會趨近某值。而 Big-O 也就是當 input size 夠大時，係數的差異就可以忽略過去。


這五種 asymptotic notation 之前就學過了，所以上課就比較沒有認真聽，不過再聽一次 Big-O 的定義時，覺得這種定義就很自然。

因為教科書上的定義問題，老師有解釋了一下，因為 computer 是離散的，但用連續函數表示比較方便，為了方便表示或是分析，有時候 n 會允許負數，雖然現實上是不可能。就方便方便~










關於定義的部分就參考講義，這裡要注意的是 Big-O 的定義和 Little-o 定義的差別，Big-O 是存在一個 c 而 Little-o 則是對每一個 c。

跟微積分一樣，證明極限值若用定義方式證明很不容易，像是扯到對數的話，這裡提供一個定理，接下來證明的話，可以用上下微分的方式來求出值...
懂概念就好，這證明也很簡單，兩邊的定義寫一下，就可以看出來相等。主要還是 O o 大於小於的觀念。