算法运行时间分析

Question

大O时间复杂度会是多少？我主要是对while循环的运行时间感到困惑。我知道两个for循环的运行时间都是O(n)。

cin >> n >> min >> max;

for(int i = min; i < n; i++) {

     for(int j = 1; j < max; j++) {

        total = 1;

        while(total < n) {

             total = total *2;

        }

    }
}

- S. James

---

http://stackoverflow.com/questions/33293998/algorithm-running-time - Mitch Wheat

括号要清晰明了。如果没有括号，则答案为O(logn)。如果您遵循Python缩进的风格来暗示嵌套循环，则其复杂度为O(nmaxlogn)。 - therainmaker

你为什么认为内部循环是O(n)？在我看来，它看起来像是O(max)。 - ajb

Answer 1

< p > 在 < code > while 循环中，< code > target 的进展是：

1 2 4 8 ... 2^P

您需要经过log(2, n)步骤 - 即以2为底的n的log值。该循环的时间复杂度为O(log n)。

- R Sahu

Answer 2

首先，看起来您忘记了加括号。在您的代码中，整个循环不在嵌套的for循环内部。现在我们有一个毫无意义的嵌套for循环，只是将total设置为1，然后是一个独立的while循环。第一个的复杂度为O((n - min) * max)，第二个的复杂度为O(log(n))。总时间复杂度是它们的总和。

可能您真正想表达的是这样的：

for(int i = min; i<n; i++) {

 for(int j =1; j< max; j++) {

    total = 1;

    while(total < n) {
         total = total *2;
    }
  }
}

在这里，我们将整个循环放在嵌套的for循环中。时间复杂度是我们之前计算的乘积，因此为O((n - min) * max * log(n))。如果min和max是常数，则可以简化为O(n log n)。

- janos