【資料結構】-時間複雜度

說實在話，這議題真的很抽象，我困擾了滿久的(我努力讓自己懂反覆看了4-5次，還是不是很清楚)。
摘一下重點：





1.O(1)或O(c)：稱為常數時間(constant time)
2.O(logn)：對數時間(Logarithmic time)
3.O(log₂n)：稱為次線性時間(sub-linear time)
4.O(log²n)：對數平方時間(Long-squared time)
5.O(n)：稱為線性時間(linear time)
6.O(n²)：稱為平方時間(quadratic time)
7.O(n³)：稱為立方時間(cubic time)
8.O(n^k)：多項式時間(Polynomial time)
9.O(2ⁿ)：稱為指數時間(exponential time)
10.O(rⁿ)：指數時間
11.O(n!)：階乘時間(Factorial time)


1(時間最短)<11(時間最長)




謎之速度=>O(n1og₂n):介於線性及二次方成長的中間之行為模式。(我不知道他該擺哪，有知道的好心人可以告訴我，謝謝XD)


Ω(omega)
對f(n)=Ω(g(n))  ->  g(n)=f(n)下限  f(n)=Ω(g(n))  ->  g(n)就是它成長的最大函數


Θ(Theta) 
f(n)=Θ(g(n))，若且唯若存在大於0的常數c1,c2和n0，使得對所有n值而言，n≧n0時，c1g(n)≦f(n)≦c2g(n)均成立。

f(n)=Θ(g(n))   ->   g(n)=f(n)的上限和下限



 Big-O取執行次數中最高次方或最大指數部份的項目即可。 如：
– 陣列元素相加為2n+3 = O(n)
– 矩陣相加為2n²+2n+1 = O(n²)
– 矩陣相乘為2n³+4n²+2n+2=O(n³)

補充：
時間複雜度 = 執行一次程式所花費的時間
空間複雜度 = 執行一次程式所佔用的記憶體空間

----------------------------------------------------------------------------------------------------------------------------------
參考:
1.時間複雜度(詳細說明)
http://content.edu.tw/senior/computer/ks_ks/book/algodata/algorithm/algo5.htm
2.Log對數(我承認自從高中畢業後，已經不太認得它了)
http://zh.wikipedia.org/wiki/%E5%B0%8D%E6%95%B8
3.這位前輩解的真清楚(基本上我只看懂：只要取最高次項, 就是它的時間複雜度. 一般的常數項, 大抵不用管，我喜歡他說「不用管」感覺=很容易)
http://www.programmer-club.com/showSameTitleN/csce/1535.html
4.簡單明瞭的說明及圖解
http://malesa.no-ip.org/teaching/97(2)/a/%E6%BC%94%E7%AE%97%E6%B3%95%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6.pdf
5.這位好心人用PHP實例計算時間複雜度非常的實用而且易懂
http://www.wretch.cc/blog/t2602567/21812744
6.維基百科的說明(好多喔~我用跳著看0.0~基本上是沒看懂Orz)
http://zh.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%9C%E6%80%A7%E7%90%86%E8%AB%96
7.時間複雜度 and 空間複雜度
http://www.blueshop.com.tw/board/show.asp?subcde=BRD20060310230058AA5&fumcde=FUM20050124191259IGD
8.時間複雜度 and 空間複雜度
http://www.programmer-club.com/showSameTitleN/cb/11710.html