[技術討論] 好急！！咩叫Big O notation?

alex24680

如題，咩叫big O notation??
如果題目係咁,咁應該點做。。。我睇完wiki都唔明
10 log(n) + 3n log(n) + 2 log log(n)

Jackass_TMxCK

n log n is the answer?

snoopy11hk

n log n is the answer?
Jackass_TMxCK 發表於 2015-1-16 08:46

    i think so

FlyingForever

概念上黎講，T(n) = O(f(n))係指「我地可以搵到一個數C，使得當n好大既時候，C*f(n)會大過T(n)」
以呢幅圖為例

紅線係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

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

big-O 係data structure / algorithms 內已經係最最最簡單既第一課，如果咁都睇唔明／搞唔掂，休想合格。。加油！！

dragonken

Bit O notation = Time Complexity

alex24680

畢左業，做左野半年。多謝大家

sapphire4890

如果唔熟prove time complexity就溫calculus

KinChungE

如果唔熟prove time complexity就溫calculus
sapphire4890 發表於 2020-6-23 21:48

正常都唔需要proof, 識分邊個大邊個細就夠