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++是一个操作,你循环n/2时间.因此,此代码执行n/2操作.因此,大O是O(n/2) = O(n)(你可以抛弃常数因子1/2).

对于其他问题,只需执行相同的操作(计算sum++执行的次数,然后通过抛出常量来简化).