資訊工程 - 演算法與資料結構 - 資料結構 - 時間複雜度(Time Complexity)

目錄:資訊工程 - 演算法與資料結構  -  Algorithm&Data Struncture(目錄)


前言

復習的話,首先得復習C語言基礎。

這個一般有專門的書會教,我們直接跳過。

從計算量開始:

  • ビッグオー (Big O
  • ビッグオメガ (Big Ω
  • ビッグシータ (Big Θ


ビッグオー (Big O

  • 表記: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³)。

留言

這個網誌中的熱門文章

【TOEIC】多益復習800分的準備 - 第2天(從600分進步到800分計劃)

微積分 - 求不定積分 $$\int \:tanxdx$$ Integral of tan x dx

【TOEIC】多益復習800分的準備 - 第4天(從600分進步到800分計劃)