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

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

n log n is the answer?

TOP

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



    i think so

TOP

概念上黎講,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)
附件: 您需要登錄才可以下載或查看附件。沒有帳號?註冊

TOP

本帖最後由 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

TOP

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

TOP

Bit O notation = Time Complexity

TOP