Re: [問卦] 學排序演算法要幹嘛？

※ 引述《anger312143 (anger)》之銘言：
: 標題: [問卦] 學排序演算法要幹嘛？
: 時間: Thu Apr 15 04:27:44 2021
:
: 如題
: 現在各大程式語言
: 幾乎每款都有內建排序套件
: 直接拉套件就好了
: 為啥還要學排序演算法
: 是要養教授還是怎樣
: 有咪有卦？
學排序演算法主要是讓你了解各種演算法的特性。
在不同的場合你會遇到的限制不一樣。

比如給你一個LinkedList，且不能使用太多的額外空間進行排序，
那多半就要採用 merge sort 這類型的演算法

從你說的「每款都有內建排序套件」，聽起來像在抱怨為什麼要學 Quick Sort？
確實 QuickSort 做法看起來是比較難懂，而且各大程式語言都有實現這做法的內建函式庫

但是，你上演算法，總是會學到 Quick Select 的對吧？
也就是要怎麼樣在一個長度為n的陣列裡面用平均o(n)的時間找到第k大的東西，(1<=k<=n)其他語言我不太確定，但是Java 的 Arrays 裡面就沒有內建這機能
Link: https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html

那既然你都要學 Quick Select 了，沒啥道理不學Quick Sort呀 做法根本就一樣

其實我猜會有這種「學這個幹嘛」的想法，通常都是因為遇到阻礙有點累。
這時候我覺得比較好的做法是聽角卷綿芽唱歌
https://youtu.be/AR6O_yi2bx8?t=2406 (Watame Ch. 角巻わため)

https://twitter.com/blueta9810/status/1378966179029508097
https://pbs.twimg.com/media/EyMRfxeVoAI98FD.jpg

這可以有效提升緩解精神疲勞、提升學習的士氣喔！

: --
: ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.31.37 (臺灣)
: ※ 文章網址: https://www.ptt.cc/Gossiping/M.1618432066.A.C6F
: 推 Nigger5566: 你適合學拍桑 04/15 04:28: 推 Ericz7000: 真的～ O(nlogn) 和 O(n^2) 不是差不多嗎？ 04/15 04:31o(nlogn) 和 o(n^2) 差多了，跟 o(nlogn) 差不多的是 o(n)

--
https://pbs.twimg.com/media/EwSsY_jVEAkCEgJ.jpg

角卷綿芽80萬訂閱紀念靠枕開始販賣！ (開放購買至 4/19 下午 4:59)
購買連結: https://hololive.booth.pm/items/2808989

--

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.234.190.206 (美國)

不會吧？ 左邊ratio是 n/logn ，右邊是 logn ，怎麼看都是左邊比較爆啊

我不太確定你想要用這圖表達什麼

https://i.imgur.com/J0EfizK.jpg

但你可以隨便代入一個大數字，比如 n = 2^32 = 4294967296 比較一下 n = 4294967296 nlogn = 137438953472 n^2 = 18446744073709551616

這件事情反映的其實是 For any p > 0, n^p/logn → ∞ as n → ∞

fixed

sorting 了不起也就花一個星期啊 XDDD

所以我使用"不能用太多額外空間"這個比較委婉的講法

o(logn) 跟 o(n) 額外空間總還是有差別嘛

※ 編輯: arrenwu (98.234.190.206 美國), 04/15/2021 07:08:40