java - for循环运行时间分析java

Question

对于所有这些，我必须找出运行时间。

1.

for ( int i = 0; i < n; i+=2 )
    sum++;

2.

for ( int i = 1; i < n; i*=2 )
    sum++

3.

for ( int i = 0; i < n; i++ )
    for ( int j = 0; j < n; j++ )
        sum++;

4.

for ( int i = 0; i < n; i++ )
    sum++
for ( int j = 0; j < n; j++ )
    sum++
// The above are two loops one after the other, NOT nested

5.

for ( int i = 0; i < 2*n; i++ )
    sum++

6.

for ( int i = 0; i < n*n; i++ )
    sum++;

7.

for ( int i = 0; i < n; i++ )
    for ( int j = 0; j < n*n; j++ )
        sum++;

8.

for ( int i = 0; i < n; i++ )
    for ( int j = 0; j < 10000; j++ )
        sum++;

---

第一个我得到 O(n)，第四个我得到 O(n^2)。这些是正确的吗？我该怎么做其他人？我真的对第二个感到困惑。

答案可以用大 O 或大 theta 表示。

Answer 1

基本上，您可以根据n.

例如：

for ( int i = 0; i < n; i+=2 )
    sum++;

sum++是 1 次操作，您循环n/2次数。因此，此代码执行n/2操作。因此，大 O 是O(n/2) = O(n)（你可以去掉 的常数因子1/2）。

对于其他问题，只需做同样的事情（计算sum++执行的次数，然后通过丢弃常量来简化）。

Answer 2

一种正式但乏味的方法，使用 Sigma 表示法（离散数学）来计算循环的增长复杂度顺序。

1. Linear

2. Logarithmic

3. Nested Independent Loops

4. Independent Loops

5. Linear

6. Quadratic

7. Independent Nested Loops

8. Independent Nested Loops