No Image

[Algorithms] The Big-O notation

November 21, 2011 Victor 0

在 Computer Science 裡面,很常的我們都沒有辦法得出一個絕對的數字來表示問題的難度或複雜度。所以我們會嘗試的用簡化的界限來表示複雜度,一方面也讓我們可以更簡單的估計程式執行大約的狀況。意思大概就是讓你知道,當 n 大概很大的時候,程式執行的複雜度差不多是怎樣?! 假設 是程式的複雜度。 (asymptotic upper bound):表示 n 夠大時, 大致上會小於 ,其中 c 是一個正的係數。 (asymptotic lower bound):表示 n 夠大時, 大致上會大於 ,其中 c […]

No Image

[Algorithms] P, NP, NP Complete, NP Hard

November 21, 2011 Victor 0

不是 Computer Science 本科生,還真是沒有辦法把 Complexity 懂得透徹。 一般我們用 P, NP, NP Complete 跟 NP Hard 來評估一個問題的複雜度,他到底是甚麼意思呢? P: 指的是有 Polynomial Time 的解的問題。 NP: 指的是還沒有找到 Polynomial Time 的解,也不確定有沒有 Polynomial […]