for循环运行时间分析java

-1

对于所有这些我必须找出运行时间。for循环运行时间分析java

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

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

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

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

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

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

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

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

对于第一个I得到了O（n），第四个得到了O（n^2）。这些是正确的吗？我该怎么做别人？我很困惑第二个。

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

基本上，你可以根据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++，然后通过抛出常量来简化）。

2014-04-21 21:39:07 jh314

非常感谢。你能快速解释第二个吗？我仍然对循环运行多少次感到困惑。 – user3558088

'我'每次翻倍。所以，如果你把'n'加倍，你可以再循环1次。 – jh314

使用西格玛符号（离散数学），一种正式但繁琐的方法来提出增长复杂性的循环顺序。

1. Linear

enter image description here

2. Logarithmic

enter image description here

3. Nested Independent Loops

enter image description here

4. Independent Loops

enter image description here

5. Linear

enter image description here

6. Quadratic

enter image description here

7. Independent Nested Loops

enter image description here

8. Independent Nested Loops

enter image description here

2014-04-22 14:33:21

回答