Thursday, August 07, 2008

What is sublinear?

有人搜尋 "what is sublinear time" 結果找到我的 blog 這邊來,看來可以發個文說明一下。

一般來講,如果 problem instance size 為 n,則 linear time 就是指 O(n)。但事實上, problem instance size 不見得就是 n,譬如一個 n 個點的圖形,如果是使用 adjacency matrix 來儲存,那麼 input size 就是 O(n^2)。所以說,假設 input size 為 O(f(n)),則 linear time 就是指 O(f(n)),這樣子也比較合理。

那什麼又是 sublinear time 呢?如果一個 problem 的 instance size 為 O(f(n)),則解決這個 problem 的演算法時間複雜度為 o(f(n)) ("little-o" of f(n)) 就稱為一個 sublinear time algorithm。little-o 的定義可以查演算法的課表,最簡單的定義就是利用 limitation 的方式。譬如 g(n) is sublinear of f(n) if 。所以如果 f(n) = n^2,則 O(nlog n)、 O(n) 都算 sublinear。

2 comments:

BarrosH said...

但是有一些模型是 query model。

也就是說沒有 input size。是否還是應該說 instance size。

Joseph, Chuang-Chieh Lin said...

其實我覺得這樣的解釋應該就夠了,尤其對初學者的話。