keen coral
假設以BigO舉例
Big-O定義如下：
O(g(n))={f(n)：存在正整數c,n0,並且對於所有n≥n0,滿足0≤f(n)≤cg(n)}
根據定義，可以將Big-O視為Big-Theta(Θ(⋅))的「上半部」，其以「簡單函數g(n)」描述f(n)在資料量夠大時，「最多」會達到怎麼樣的趨勢。
那這樣以f(n)=6n+4為例，若選g(n)=n,c=7,n0=4，即可滿足：
0≤6n+4≤7n,∀n≥4，
表示f(n)之「上界」趨勢能夠以g(n)=7n描述。
可是若選g(n)=n², c=1,n0=7
0≤6n+4≤n²,∀n≥7 同樣符合定義，那這樣f(n)=6n+4=O(g(n))
這個g(n)是唯一的嗎?
keen coral
f(n)=n
n=O(2n)
n=O(n²)
觸嗎?
如果觸，那問題通常就是問f(n)=?O(g(n))嗎?
keen coral
只是演算法很常會說big-o，但其實是在說big-theta
Big-theta是 c1g(n)<f(n)<c2g(n)
不過要同時符合好像就是你說得這樣了
最narrow的bound
uncut orbit
假設以BigO舉例
Big-O定義如下：
**O(g(n))={f(n)：存在正整數c,n0,並且對於所有n≥n0,滿足0≤f(n)≤cg(n)}**
根據定義...
按照這個定義並不表達「最多會達到什麼趨勢」
因為那個 g(n) 可能完全達不到
能表達的應該是「最多不會超過什麼趨勢」
然後這當然是沒有唯一性的
keen coral
欸...然後我要怎麼標已解決...
stone hollow