Re: [請益] 演算法的相關知識?

看板Soft_Job作者 (Malicious Racist)時間2年前 (2021/10/18 18:01), 編輯推噓9(907)
留言16則, 13人參與, 2年前最新討論串2/3 (看更多)
我剛剛在想你的問題,我也玩python,show一下我自己寫的東西: https://i.imgur.com/kYe62pG.png
據我所知,算質數只要檢查到n^1/2的floor就好(也就是n開根號再取地板), 這是以前高中數學的內容了。其實你不用檢查到n的,這樣做你可以省下一半 要執行的敘述。 我把n這個數字給十萬,結果不到兩秒就算完了。我的電腦cpu是intel i7-4790 其實也很舊了。n給一百萬,那要花久一點,大概五到六秒鐘。 我想這就是演算法的魅力所在了,要去念數學! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.87.82 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1634551260.A.9C3.html

10/18 18:05, 2年前 , 1F
原來這id真的會寫代碼
10/18 18:05, 1F

10/18 18:41, 2年前 , 2F
看樓上才發現id
10/18 18:41, 2F

10/18 18:54, 2年前 , 3F
這寫法超慢
10/18 18:54, 3F

10/18 19:06, 2年前 , 4F
了解一下 Sieve of Eratosthenes?
10/18 19:06, 4F

10/18 19:12, 2年前 , 5F
靠 原來是常識 我數學沒學過這個… 高職數學沒教啊 幹
10/18 19:12, 5F

10/18 19:23, 2年前 , 6F
PRIMES is in P
10/18 19:23, 6F

10/18 20:18, 2年前 , 7F
常識==
10/18 20:18, 7F

10/18 20:57, 2年前 , 8F
跟2*3*7*…*23互質的話再做後面的test,不然慢到哭
10/18 20:57, 8F

10/18 21:30, 2年前 , 9F
n - sqrt(n) != n/2...
10/18 21:30, 9F

10/18 21:35, 2年前 , 10F
工程法:算一遍記起來,查表 。之後全部 O(1),更快。
10/18 21:35, 10F

10/18 22:09, 2年前 , 11F
然後就會被面試官噴了, 要不要什麼東西都做個表, 都 O(1)?
10/18 22:09, 11F

10/18 22:30, 2年前 , 12F
樓上,那叫做動態規劃
10/18 22:30, 12F

10/18 22:33, 2年前 , 13F
若時間瓶頸點早於空間,那確實用空間換時間是一個Approach
10/18 22:33, 13F

10/18 22:35, 2年前 , 14F
另外有個折衷的算法叫布隆過濾器,也挺有趣的
10/18 22:35, 14F

10/18 23:51, 2年前 , 15F
算過了就別算了
10/18 23:51, 15F

10/19 00:35, 2年前 , 16F
推查表XDDD
10/19 00:35, 16F
文章代碼(AID): #1XRKNSd3 (Soft_Job)
文章代碼(AID): #1XRKNSd3 (Soft_Job)