确定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。这是算法本身的属性，无论它运行的是实际的机器，这就是为什么它很重要。