作者: alex24680 時間: 2015-1-16 01:47 標題: 好急！！咩叫Big O notation?
如題，咩叫big O notation??
如果題目係咁,咁應該點做。。。我睇完wiki都唔明
10 log(n) + 3n log(n) + 2 log log(n)
作者: Jackass_TMxCK 時間: 2015-1-16 08:46
n log n is the answer?
作者: snoopy11hk 時間: 2015-1-16 21:15
n log n is the answer?
Jackass_TMxCK 發表於 2015-1-16 08:46
i think so
作者: FlyingForever 時間: 2015-1-16 23:02
概念上黎講，T(n) = O(f(n))係指「我地可以搵到一個數C，使得當n好大既時候，C*f(n)會大過T(n)」
以呢幅圖為例
[attach]1754678[/attach]
紅線係T(n) = n^3 + 10000n^2 + 1
藍線係f(n) = n^3
紫線係g(n) = 4n^3
可以見到，雖然一開始紅線既數值最大，但當n大過10000左右，紫線就會一直大過紅線
呢種情況，我地就會話T(n) = n^3 + 10000n^2 + 1 = O(n^3)
作者: Jackass_TMxCK 時間: 2015-1-16 23:16
本帖最後由 Jackass_TMxCK 於 2015-1-17 00:03 編輯
Big O係一個好大概咁去睇個algorithm行ge時間成本，各個時間成本中最大個part係個樽頸，所以Big O係揀最大影響個個，因為係好大概所以如果係：2n log n咁樣樣個2係無用，n log n就已經夠。
好似你個問題咁，最影響ge係 n log n個舊，揀好之後再淨化佢清走d多餘野就變成答案n log n
總之就係最大最大個個variable扣除coefficient
n^n>n!>n^x>n log n>n> logn >1(排錯唔洗hi，講醒就得我改)
利申Data Structure麻麻地，有錯請講
from wiki:
http://zh.wikipedia.org/wiki/%E5 ... D.E6.95.B0.E9.98.B6
作者: s.friday1004 時間: 2015-1-17 09:26
big-O 係data structure / algorithms 內已經係最最最簡單既第一課，如果咁都睇唔明／搞唔掂，休想合格。。加油！！
作者: dragonken 時間: 2015-1-17 10:51
Bit O notation = Time Complexity
作者: alex24680 時間: 2020-6-23 21:26
畢左業，做左野半年。多謝大家
作者: sapphire4890 時間: 2020-6-23 21:48
如果唔熟prove time complexity就溫calculus
作者: KinChungE 時間: 2020-6-23 22:34
如果唔熟prove time complexity就溫calculus
sapphire4890 發表於 2020-6-23 21:48
正常都唔需要proof, 識分邊個大邊個細就夠
作者: louislam 時間: 2020-6-23 22:35
畢左業，做左野半年。多謝大家
alex24680 發表於 2020-6-23 09:26 PM
笑咗，5年半後先多謝返
作者: sapphire4890 時間: 2020-6-24 08:54
回復 10 #KinChungE
巷大校友都咁講既咩
無理由架
2121 2119 3250 都要proof
via HKEPC Reader for Android
作者: sapphire4890 時間: 2020-6-24 10:16
笑咗，5年半後先多謝返
louislam 發表於 2020-6-23 22:35
笑左, 原來係5年前既post.
作者: rabbit82047 時間: 2020-6-24 10:43
笑咗，5年半後先多謝返
louislam 發表於 2020-6-23 22:35
都算有心, 過五年半都記得返黎多謝返
作者: fatdog 時間: 2020-6-24 14:10
畢左業，做左野半年。多謝大家
alex24680 發表於 2020-6-23 21:26
5年啦，你重記得要返黎say thank you
作者: KinChungE 時間: 2020-6-24 14:10
回復 KinChungE
巷大校友都咁講既咩
無理由架
2121 2119 3250 都要proof
via HKEPC ...
sapphire4890 發表於 2020-6-24 08:54
理論同實踐係兩回事
作者: toylet 時間: 2020-6-25 01:39
提示: 作者被禁止或刪除 內容自動屏蔽
作者: alex24680 時間: 2020-6-26 09:02
回覆 11# louislam
無計用左5年先grad到
作者: alex24680 時間: 2020-6-26 09:04
回覆 16# KinChungE
讀來都係為老豆老母開心
作者: toylet 時間: 2020-6-27 02:58 標題: 認真讀書 是 為了 ....
提示: 作者被禁止或刪除 內容自動屏蔽
作者: faiwaic 時間: 2020-6-29 14:26
其實工作上真係會 apply 到??
作者: sapphire4890 時間: 2020-6-30 20:59
其實工作上真係會 apply 到??
faiwaic 發表於 2020-6-29 14:26
不如問下自己咩level先
作者: EITCo 時間: 2020-6-30 22:00
其實工作上真係會 apply 到??
faiwaic 發表於 2020-6-29 14:26
我見過人將明顯係 n^4 的問題用 n^8 的寫法
(雖然實際應用個n未必好大，但話唔埋，而且去到8次方)
所以唔係日日有用
但你唔識留意幾時個algorithm真係好重要
咁就只係個唔合格的engineer
有時用i9都窒可能就係咁解
作者: toylet 時間: 2020-6-30 23:23
提示: 作者被禁止或刪除 內容自動屏蔽
作者: LoneGumMan 時間: 2020-7-1 00:34
回覆 24# toylet
超多 transaction 都係 LINEAR..
如果你係因為 log(n) vs log(n^3)...少少野已經可以好大鑊.
作者: toylet 時間: 2020-7-1 00:37
提示: 作者被禁止或刪除 內容自動屏蔽
作者: LoneGumMan 時間: 2020-7-1 00:45
其實工作上真係會 apply 到??
faiwaic 發表於 2020-6-29 14:26
絕對用到..
你答唔答到點解 standard quick sort , 去到十零個 element 之後會變用 bubble sort?
=====
有時你寫一個 implementation , 你會好快咁選一個 用一個LOOP 去到...
三個月之後, 有人問你, 點解你唔用 第二個 algorithm 做? O(log N) vs O(n) 喎..
你如果可以話佢知, average case N = 2.. O(log N) 果邊個, 可能有十九幾個 function call, constant 大好多喎..你CALL 得黎我都LOOP 完喇.
你如果真心想提升實力, 就需要真正去理解學問背後O既道理..
作者: toylet 時間: 2020-7-1 01:12
提示: 作者被禁止或刪除 內容自動屏蔽
作者: faiwaic 時間: 2020-7-1 07:38
不如問下自己咩level先
sapphire4890 發表於 2020-6-30 20:59
我只係煮到埋黎就食，有需要就現學現用咁囉。
IT 就係做到老學到老。
作者: LoneGumMan 時間: 2020-7-1 15:58
呃學費 做功課 就用 sorting 來教 Big O!
除非 特別情況, 現實**無人**會 自己 寫 sorting, 特別是有 RDBM ...
toylet 發表於 2020-7-1 01:12
關有冇database 乜野事？
問題係你明唔明 big-O 唔代表一切，佢隔離有個constant.
就用database 黎做例子。好多人睇query plan,一味淨係識話“咦？點解會做scan 架唔中index 喎，梗係慢啦”，跟住死加爛加 index，但係個 database 都係唔揀黎用，又或者呢 part 用左新index第二part 慢,可能完全冇諗過個database真係知道scan 唔一定係最慢.
你話冇人會自己寫sorting, 啱。但係俾幾個map /set implementation你，你識唔識得揀幾時用邊款？又可唔可以為自己既決定辯護？
作者: toylet 時間: 2020-7-1 20:04
提示: 作者被禁止或刪除 內容自動屏蔽