作者iamfedal (最愛是你)
看板Army-Sir
標題[問題] 排序法的複雜程度??
時間Tue Jan 17 12:41:38 2012
想請問一下 做到一些題目
問說一些像氣泡法O(n^2) 快速法O(n log2n)
選擇法O(n^2) 插入法O(^2)
二元術法O(n log2n) 堆積法O(nlog2n)
問說之間的時間複雜度比較是要怎麼比啊
1.有一年題目是比較
O(1) O(n^2) O(log2n) O(2^n)的比較是要怎麼比啊??
2.為什麼在一個堆級(heap)資料結構上搜尋最大值的時間複雜度為O(1)啊
3.96年第13提:時間複雜度的比較何者錯誤?
(A)log2n < n < nlog2n
(B)nlog2n < n^3
(C)n^2 < n^3 < 2^n
(D)2^n < nlog2n < n^2
答案是(D) 書上寫的解答為 2^n < n^2 < nlog2n
這樣不就跟C矛盾了嗎 有人可以解答嗎QQ
4.還有速度較快的 時間複雜度會較複雜嗎??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.232.117.46
1F：→ Durant35:我也想問這個...數學不好 01/17 12:47
2F：推 CHICIOGARY:答案錯了吧 2^n最大啊 01/17 13:00
3F：→ LaPAELLA:1 畫圖看最簡單 2.我怎麼記得是O(nlogn) 3. 你寫反了 01/17 13:00
4F：→ CHICIOGARY:或者可以把n帶入比較大的數值檢驗 01/17 13:02
5F：推 linchen1:3應該是 2^n > n^2 > nlog2n 01/17 13:03
6F：→ idow:買書的吧? 01/17 13:20
7F：推 heartsky7:XDDD 01/17 13:39