算法分析运行时间

Question

big-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;

        }

    }
}

Answer 1

target在while循环中的进度是：

1 2 4 8 ... 2^P

您需要 log(2, n) 个步骤 -- 即 n 中的 log 个基础 2。该循环是 O(log n).

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)

算法分析运行时间

analysis of algorithm run time

java

c++

algorithm

runtime

算法分析 运行 时间

analysis of algorithm run time

java

c++

algorithm

runtime

算法分析运行时间