大O，大歐米茄，大theta函數

Question

This is the question

我以一個數據結構類，我是如何與這種類型的問題去那種迷茫。任何線索都會有幫助，提前謝謝。

Answer 1

讓我解釋其中之一，看看你是否可以嘗試其餘的。

f(n) is O(g(n)) "function f of n" is ("big O") **Order** g(n) 

if for some n (maybe not f(0) or f(1) or... but eventually for some n) 
and for some **constant** (1, 2, 50, 80 million, something) 

f(n) <= c * g(n) 

So if we say some function f is "O(log n)" than means that starting at 
some n that we pass into f(), and some number c then 

    f(n) <= c * log(n) 

讓我們一個非常簡單的例子：

function f (n) { 

    answer = 0; 
    for (i = 0; i < n; ++i) {  // loops n times 
     answer += n+3;    // 2 ops: add, add 
     answer /= (7*n);    // 2 ops: mult, div 
     answer ^= 2;     // 1 op: xor 
    }         // 2 + 2 + 1 = 5 
    return answer; 
} 

所以，我們可以說 'C' 是5，和g（n）是N（我們清楚地循環n次）。

f (n) <= 5 * g(n) 
f (n) <= 5 * n 

f() is O(n) 

基本上這是說什麼，當n變得足夠大時，常數因子根本就不重要。如果f（n）是（5n）或（7n）或（27n），當我們可以將其與其他函數（87log（n））或（0.01n 2）進行比較時，它幾乎沒有區別。

 \ n 10  1000  100000 
f(n) \----------------------------- 
    7n | 70  7000  700000  O(n) grows linearly with prob size 
87logn | ~200  ~600  ~1000  O(log n) grows slowly [good!] 
.01n² | 10 10000 100000000  O(n²) grows fast [bad!]