淡江大學

#新手 O(n)比較O(n log n)

6月11日 14:38
為什麼O(n)總是比O(n log n)好呢? 我的疑惑: 已知O(10 n)=O(n)可以省略係數 當 n=1024 O(n log n) = O( 1024 * log(1024) ) = O(1024 * 10) = O(n * 10) = O(n)? 這樣如果n又小於1024的話, O(n log n) = O(8 * log(8) ) = O(8*3) 不就比 O(n) = O(10n) = O(10 * 8) 還要好嗎? 自學演算法中,還請各位解惑
6
回應 20
文章資訊
共 20 則留言
O(n) 並沒有總是比 O(nlogn) 好啊 你的前提就已經錯了 bigO 只是描述增長的速度而已 具體哪個演算法更好用 是根據具體狀況而定的 舉例來說 quicksort 大部分狀況下最快 但當隨機存取的成本太高(例如鏈結串列) 那我們可能就會改用 mergesort 當記憶體使用的成本更高 可使用不必遞迴的 heapsort 同樣都是 O(nlogn) 使用的時機也不一樣 另外 當整個序列幾乎排好的時候 O(n^2) 的 insertion sort 是最快的 而當序列內的元素範圍很小時 counting sort基本上是一個 O(n) 的狀況
沒有總是吧 只是增長型態
大同大學 資訊工程學系
O(n log n)=O(10 * 1024) ?????????
國立清華大學
你的 n 怎麼一邊代 1024 一邊代 10 (更:原來是亂換左右順序= =)
b3 b4 n * log(n) = 1024 * log(1024) = 1024 * 10 = 10 * 1024 有什麼不對嗎???
國立清華大學
B5 等式後面不成立啊 O(10 * 1024)=O(10 n)
國立清華大學
B0 B5 重新整理一遍 自己看問題在哪 列算式維持原本相對位置不是基本的嗎? 這樣別人看不清楚 當 n=1024 O(n log n) = O( 1024 * log(1024) ) = O(1024 * 10) = O(n * 10) = O(n)? 這個 10 是從 n 來的 不是 constant 不能化簡
B7 我沒有說他化簡是對的 但你們確實是沒有看清楚不是嗎 冷靜一點好嗎 另外 B6 我沒有改留言 講話要拿出證據
國立清華大學
B8 如果不覺得是對的你在回什麼?🤔 我當初看是有改啦 反正沒證據 這也不重要
原 PO - 淡江大學
B7 不好意思是我沒有按照順序打好,我想表達的意思按照你的格式又重新發問了一次,雖然以O(n * log n)、O(n)的角度看知道 log n是不能省略的,但如果算出值之後,大小比位仍然相同嗎?
原 PO - 淡江大學
B1 謝謝你提供實作上會遇到的一些想法,主要是疑惑O(n)及O(n log n)的差異在哪, 如果又加上係數,捨棄O(n log n)堅決採用O(n)的可能性存在嗎? 還是就要看程式的需求呢?就是你提到的使用時機不同 我看交大OCW演算法提到,fibonacci heap及binary heap,fibonacci heap的係數很高所以不一定就比較好
REF. Lec13 演算法 第九週課程 (1/2) (已經設定開始於17:35)
B11 我的理解是 bigO 只描述了花費的時間是怎麼隨著資料大小的增長而增長 而不全然代表誰好誰壞 而之所以常數可以被省略 就是因為「和n成正比」、「和10n成正比」意思是一樣的 舉個誇張一點的例子 a 是一個 O(n) 的排序演算法 假設排10個數字要一個小時 20個數字要兩個小時 30個數字要三個小時 b是一個O(n^2)的排序演算法 排10個數字要一毫秒 20個數字四毫秒 30個數字九毫秒 以這兩個想像出來的怪異排序法來看 明顯在大多數情況下 b都會遠快於a 儘管O(n)理論上應該要快於O(n^2) 不知道有沒有回應到你的想法 我其實蠻不擅長解釋的
國立臺灣科技大學
隨便找一個網站
所以沒有總是比較好@@ 就是想表達量級關係而已
國立中央大學 資訊工程學系
首先我建議原po要先了解那個“logN”是怎麼來的 不是亂代數字進去 常數可以消掉的原因是因為它和增長的“斜率”(我自創的名詞)無關故可以消掉 logN的由來是來自於binary tree serch的概念 每一次往下找都可以砍掉一半的資料 所以實際上還是和input data有關 ---- 補充一下 所以O(N)和O(NlogN)差別在 前者每一筆資料都處理一次 後者除了每一筆資料都處理一次以外 還要去做一次砍一半資料的動作 最經典的NlogN演算法就是quick sort 可以參考看一下每一個input data它內部是怎麼處理的
匿名
這則留言已被刪除
6月12日 12:58
已經刪除的內容就像 Dcard 一樣,錯過是無法再相見的!
國立中山大學
B1 補充一下:insertion sort 在best case 是O(n)
國立清華大學
他說的是成長的速度耶 10n 跟 nlogn 你n帶8進去10n比較大,但你帶個一億進去肯定nlogn比較大阿
演算法是大概,並且以最壞結果,Google 曲線圖可以看到!
國立成功大學
沒事 當n趨近無限大就沒問題了
國立交通大學 資訊工程學系
要回到複雜度的定義,不嚴謹的複述: 在 n->無限大的時候,架設 F(n) in Theta(G(n)) 則存在常數 a, b 使 aG(n) <= F(n) <= bG(n)