使用 if 语句的嵌套循环的时间复杂度

Question

我正在学习 class 高级 C++，但我在尝试找到锁定在 if 语句后面的嵌套 for 循环的 Big-Θ 时遇到了困难。不幸的是，我的教授（出于某种奇怪的原因）只是希望我们从预先要求 class 中了解这一点（即使我在另一所大学学习了不同的课程内容）并且不会花时间教我。

我不想让任何人帮我解决我的作业，我真的很想学习这些概念，所以我在下面创建了我自己的独特功能。考虑到第二个循环只运行几次，我无法确定这种类型的函数是 Θ(n) 还是 Θ(n^2)。任何一般性解释或可能是我如何解决这些类型问题的正确方向的指针将不胜感激:)

注：假设变量n为任意大小的正整数。

int count = 20;
for (int i = 0; i < n; i ++) {
    if (i == count) {
        for (int j = 0; j < count; j++) {
            // Some O(1) code
            // Maybe a print to console or something
        }
        count *= 2;
    }
}

Answer 1

您需要问的第一个问题是，您在数什么？通常你可以找到一些像样的东西来计算，而不仅仅是“说明”，以获得一个好的猜测。获得大 O 值后，您可以仔细检查该值是否正确。

int count = 20;
for (int i = 0; i < n; i ++) {

好的，这显然运行了 O(n) 次。

    if (i == count) {

第一次通过时，输入 O(n/20) 次。这可能会改变。

        for (int j = 0; j < count; j++) {

这运行 O(count) 次。

            // Some O(1) code
            // Maybe a print to console or something
        }

        count *= 2;

现在这变得有趣了。每次计数加倍。

所以第一个内循环在 20 个外循环之后运行，然后 20 O(1) 工作。

计数翻倍。第二个内部循环在 40 个外部循环之后运行，并执行 40 O(1) 的工作。

计数翻倍。第三个内部循环在 80 个外部循环之后运行，并执行 80 O(1) 的工作。

计数翻倍。第四个内循环在160个外循环之后运行，在内循环中做160 O(1)。

现在你必须把它变成数学。你可以猜测，然后检查。但是假设你猜不出来？

好吧，绘制它！

 n   |    inner steps
------+----------------
  20  |    20
  40  |    20+40 = 60
  80  |    20+40+80 = 140
 160  |    20+40+80+160 = 300
 320  |    20+40+80+160+320 = 620

把它扔到绘图程序上。图表 看起来像什么 ？如果它弯曲，取对数可能会给你斜率，你可以从中找到多项式的指数。

记得使用散点图。您根本不在乎 60、100 或 240 时会发生什么。你关心的是峰值，它发生在 20 和每次翻倍时。散点图会降低您绘制的点。

还要计算外循环步骤和与计数的比较，以确保它们不是很大。

一旦你有了假设，想办法证明你的答案是正确的。

使用 if 语句的嵌套循环的时间复杂度

Time complexity of nested loops with if statement

c++

runtime

time-complexity