資訊工程 - 演算法與資料結構 - 資料結構 - 時間複雜度（Time Complexity）
目錄：資訊工程 - 演算法與資料結構 - Algorithm&Data Struncture（目錄）
前言
復習的話，首先得復習C語言基礎。
這個一般有專門的書會教，我們直接跳過。
從計算量開始：
- ビッグオー （Big Ｏ）
- ビッグオメガ （Big Ω）
- ビッグシータ （Big Θ）
ビッグオー （Big Ｏ）
- 表記：f(n)=O(g(n))
- 意味：f(n)的發散速度最快的話，可以與g(n)相等。（即再快也不高於）
- 定義：存在n0，C，當n>n0時，|f(n)|≤C|g(n)|
- 例：4n³+1=O(n³), 4n³+1=O(n⁴)
爲什麽要這麽寫？假設你寫了個算法，它要3秒運行。你不能直接說它要3秒。因爲不同的環境跑出來的結果不一樣，所以我們要用這種抽象的公式來表示。
我們把這種記述的方法叫做，O記法（オーきほう、オーダーきほう）。
ビッグオメガ （Big Ω）
表記：f(n)=Ω(g(n))
意味：f(n)的發散速度就算最慢，可以與g(n)相等。（即再慢也不低於）
定義：存在n0，C，當n>n0時，|f(n)|≥C|g(n)|
例：4n³+1=Ω(n³), 4n³+1=Ω(n²)
ビッグシータ （Big Θ）
表記：f(n)=Θ(g(n))
意味：f(n)和g(n)大致相等的發散速度。
定義：存在n0，C1，C2，當n>n0時，C1|g(n)|≤|f(n)|≤C2|g(n)|
例：4n³+1=Θ(n³), 2n+3ⁿ=Θ(3ⁿ)
代表的なオーダー
以下由效率從高到低排列：
- O(1)
- O(logn)
- O(n)
- O(nlogn)
- O(n²)
O(1)：表示命令數和數據數無關，是定數。
O(logn)：數據數是n的時候，2乘以Step數的定數倍是計算量。二分木（英: binary tree）是典型的例子。
O(n)：表示命令數與數據數成比例。比如2*n，3*n。具體的話，n回，又或，n作爲比例的回數進行loop循環處理這樣的情況。O(nlogn)：像合并排序，二分木那樣將數據分割，並加上，把他們的數據全體用綫性搜索所需要的計算量。二分木的オーダー(logn) 乘以 綫性搜索的オーダー(n)所獲得的nlogn的計算量。
O(n²)：比如2*n²+3*n+1，這個時候，你得著眼該式的最高次項，比如是2*n³那你就寫成O(n³)。
留言
張貼留言