唸到現在實在太累，先memo個，等等寫進notion裡面。算是邊唸課本邊唸其他人提供的比記吧。
- 有關時間複雜度分析的原因是因為如果你對同個功能的code但是不同撰寫風格進行純樹上的時間測量，純數上會不一樣
- 所以會需要一個準則來歸類哪些時間複雜度是相同的。
參數傳遞方式:
- call by value 傳至副函式時，仍需在執行期時根據data大小來複製一模一樣的data
- call by address 傳至副函式時，只需要傳入一個位址參數來接data的起始位址
- call by name
- call by value result
Asymptotic Notation: 表示時間函數的growth rate(成長速率)，並且隨著input size = n的等級變化
- 有關時間複雜度分析的原因是因為如果你對同個功能的code但是不同撰寫風格進行純樹上的時間測量，純數上會不一樣
- 所以會需要一個準則來歸類哪些時間複雜度是相同的。
參數傳遞方式:
- call by value 傳至副函式時，仍需在執行期時根據data大小來複製一模一樣的data
- call by address 傳至副函式時，只需要傳入一個位址參數來接data的起始位址
- call by name
- call by value result
Asymptotic Notation: 表示時間函數的growth rate(成長速率)，並且隨著input size = n的等級變化
掰噗~
問
蛤?
時間複雜度的等級or大小:
常數等級 ⇒ 對數 ⇒ 多項式 ⇒ 指數 ⇒ 階乘 ⇒ 指數又是指數
時間複雜度的特別例子:
- $(log\ n)^{log\ n}$ 比下面大。比多項式來得大，比指數來得小。
- $log\ (n!$) 比上面小。比多項式來得大，比指數來得小。
- $2^{\sqrt{2log\ n}}$。比對數來得大，比多項式來得小。
- $n^{\frac{1}{log\ n}}$。常數等級。
所以上面時間複雜度的排序由小至大為:
常數等級, $n^{\frac{1}{log\ n}}$ ⇒ 對數 ⇒ $2^{\sqrt{2log\ n}}$ ⇒ 多項式 ⇒ $(log\ n)^{log\ n},log(n!)$ ⇒ 指數 ⇒ 階乘 ⇒ 指數又是指數
常數等級 ⇒ 對數 ⇒ 多項式 ⇒ 指數 ⇒ 階乘 ⇒ 指數又是指數
時間複雜度的特別例子:
- $(log\ n)^{log\ n}$ 比下面大。比多項式來得大，比指數來得小。
- $log\ (n!$) 比上面小。比多項式來得大，比指數來得小。
- $2^{\sqrt{2log\ n}}$。比對數來得大，比多項式來得小。
- $n^{\frac{1}{log\ n}}$。常數等級。
所以上面時間複雜度的排序由小至大為:
常數等級, $n^{\frac{1}{log\ n}}$ ⇒ 對數 ⇒ $2^{\sqrt{2log\ n}}$ ⇒ 多項式 ⇒ $(log\ n)^{log\ n},log(n!)$ ⇒ 指數 ⇒ 階乘 ⇒ 指數又是指數
如果覺得不熟悉，記得回去看基本數學公式和常用對數公式!
$O,\Theta,\Omega,o,\omega$這五種漸進式符號對於時間複雜度非常重要，要熟記定義!
彼此之間的關係可以聯想到數學式的關係(小於等於、大於等於、夾在中間、嚴格小於、嚴格大於)，進而聯想到離散數學有學過的relations的性質:
- Transitivity (遞移性)
- Reflexivity (反身性)
- Symmetry (對稱性)
- Transpose Symmetry (類似若A小於等於B，則B大於等於A)
$O,\Theta,\Omega,o,\omega$這五種漸進式符號對於時間複雜度非常重要，要熟記定義!
彼此之間的關係可以聯想到數學式的關係(小於等於、大於等於、夾在中間、嚴格小於、嚴格大於)，進而聯想到離散數學有學過的relations的性質:
- Transitivity (遞移性)
- Reflexivity (反身性)
- Symmetry (對稱性)
- Transpose Symmetry (類似若A小於等於B，則B大於等於A)
