確定Java代碼的大O

Question

我的計算機科學教授今天開始教我們關於大O符號的問題，我很難理解它。下面是他給我們的例子：

1. 什麼是下面的大O：

   一個。 4n2 + 2是：O（n^2）？

   b。 n2 + 14n + 6是：O（n^2）？

   c。 5n3 + 10n2 - n - 8是：O（n^3）？

   d。 3n2 + 2n是：O（n^2）？

據我所知，它與程序要多長時間運行基於輸入和多少將取決於輸入變化增加拿去做。我查了一個方法來確定上述問題的大O，並把我以爲是的。但是當談到確定Java代碼的大O時，我迷失了方向。有人能指出我對這些問題的正確方向嗎？

3. int count = 0; 
for (int i = 1; i <= n; i++) { 
i = n; 
count += 1; 
} 
// end for 

4. int total = 0; 
for (int i = 1; i <= n; i++) { 
for (int j = 1; j < i; j++) { 
    for (int k = 1; three < j; j++) { 
total += 1; 
} //end for } // end for } // end for 

5. int total = 0; 
for (int one = 1; one <= n; one++) { 
    for (int two = 1; two < n; two++) { 
    for (int three = 1; three < 10; three++) { 
total += 1; 
} //end for } // end for } // end for 

6. int total = 0; 
for (int pass = 1; pass <= n; pass*=2) { 
total += 1; 
} 
// end for 

7. p = n; 
while (n>1) { 
n = n/2; 
    while (p>0) { 
    p = p - 1; 
} 
// end while } // end while 

8. for (int i = 1; i <= n; i+=2) { 
j=1; 
while(j < n) { 
j = j + 2; 
x = x + 2; 
} // end while } // end for 

Answer 1

說起容易，你需要計算你的代碼沒有多少操作取決於ñ只保留震級最高爲了的的ñ功能，投擲常數之遙。所以在你的情況下，最高度的多項式。

E.g.此代碼：

for (int i = 0; i < n; ++i){ 
    System.out.println(i*2); 
} 

具有Ñ迭代和每次迭代一個操作，再加上初始化i = 0，所以N *一個總共+ B操作，其中B = 1（警告：不是真的， 見下文）。

現在，如果你在運行很有趣，你可以將多個這種由個體經營的時間，但具體數目尚不清楚，而且可以通過很多東西，如現金記憶的影響，所以我們只是說，這是另一個常數。

但是，a和b實際上很難確定。比方說++i是一項操作，i*2是另一項，而println是第三項，所以每次迭代操作3次。但它是正確的嗎？ println有多少操作？如果我們用一個符號編寫的某些操作導致幾個實際操作會怎樣？

幸運的是，這些參數並不重要了大O表示法：

• 形式一* F的所有功能（N）屬於同一類。
• 函數S（N）= A * F（N）+ B * G（N）屬於最高等級出F（n）和G（N）

現在什麼確定的f（n）的階數高於g（n）？輕鬆地說起來，這意味着F（N）總是比克（N）較大一些ň開始，即使您運行F（N）一個快速的電腦和g（上n）慢一點。

讓我們假設第一個算法有n^2操作和第二個10 * n操作。從開始n> 10第一個算法較慢（考慮到每個操作需要相同的時間，例如= 1）。所以，你用一臺電腦運行n^2算法的速度提高了100倍。現在它跑得快得多：在n^2/100時間！然而，從n> 1000開始，它變得慢於n -algorithm。無論您的計算機運行速度如何，n^2算法在足夠大的情況下總是會變得更慢n。這是算法本身的屬性，無論它運行的是實際的機器，這就是爲什麼它很重要。