Re: [問題] 排序法的複雜程度??

看板Army-Sir作者ifmama (伊夫媽媽)時間12年前 (2012/01/17 13:16)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串2/2 (看更多)

先說,離這個太久遠了可能會錯,有錯快糾正我orz ※ 引述《iamfedal (最愛是你)》之銘言： : 想請問一下做到一些題目 : 問說一些像氣泡法O(n^2) 快速法O(n log2n) : 選擇法O(n^2) 插入法O(^2) : 二元術法O(n log2n) 堆積法O(nlog2n) : 問說之間的時間複雜度比較是要怎麼比啊就數學上的比較啊.. 定義上是成長的幅度,n趨近於無限大的時候(記得是這樣,總覺得有錯比較方便的比法是代一個很大的數進去比 : 1.有一年題目是比較 : O(1) O(n^2) O(log2n) O(2^n)的比較是要怎麼比啊?? O(1)是常數,所以最小,畫在座標圖上是一橫線不會成長 n^2跟2^n代10就好一個是100一個1024,顯然後面大;代更大的數,差距只會更大 O(log2n)約略等於O(log n),又O(log n) < O(n^2) → O(log2n) < O(n^2) ↑因為只差在常數係數所以我才這樣說排一排就是 O(1) < O(log2n) < O(n^2) < O(2^n) : 2.為什麼在一個堆級(heap)資料結構上搜尋最大值的時間複雜度為O(1)啊忘了0.0a : 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 口開錯邊了吧... 2^n > n^2 > nlog2n 才對 : 4.還有速度較快的時間複雜度會較複雜嗎?? 這句話感覺很奇怪..? 速度比較快時間複雜度會比較小,硬要說比較簡單也是可以.只是會有人說簡單跟複雜嗎 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.235.116

推

book8257

01/17 13:23, , 1^F

01/17 13:23, 1^F

※ 編輯: ifmama 來自: 140.113.235.116 (01/17 13:26)

推

assyrian

01/17 13:49, , 2^F

01/17 13:49, 2^F

→

ifmama

01/17 13:50, , 3^F