根据 Big theta 分析时间复杂度

Question

我一直在尝试设置有关遍历 i 和 j 的明确信息，但是在尝试理解 while 循环时我卡住了？有人可以给我一些有关如何解决此类问题的信息吗？

Answer 1

为了计算所有time-complexity的代码，将每个循环替换为求和。此外，考虑第二个循环运行 (n - i)/3 因为 j 随着步长 3 减小。所以我们有：

Answer 2

免责声明：此答案冗长且过于冗长，因为我想为 OP 提供 "baby-steps" 方法而不是结果。我希望她能从中找到一些帮助-是否需要。

如果您在尝试一次性推导出复杂性时遇到困难，您可以尝试将问题分解成更容易推理的更小的部分。在这种情况下，引入符号有助于构建您的思维过程。

让我们为内部 while 循环引入一个符号。我们可以看到起始索引 j 取决于 n - i，因此此循环执行的操作数将是 n 和 i 的函数。让我们用 G(i, n).
外层循环只依赖于n。让我们用T(n).
现在，让我们写下 T(n) 和 G(n, i) 之间的依赖关系，只推理外循环 - 我们不关心内循环 while对于这一步，因为我们已经在函数G中抽象了它的复杂性。所以我们选择：

T(n) = G(n, n - 1) + G(n, n - 2) + G(n, n - 3) + ... + G(n, 0) = sum(k = 0, k < n, G(n, k))
现在，让我们关注函数G。
- 让我们引入一个额外的符号，并在 while 循环执行的第 t 次迭代处写入 j(t) 索引 j 的值。
- 我们调用 k 违反 while 循环不变量的 t 的值，即最后一次评估条件。
- 让我们考虑一个任意的 i。如果有帮助，您可以尝试使用 i 的几个特定值（例如 1、2、n）。

我们可以这样写：

    j(0) = n - i
    j(1) = n - i - 3
    j(2) = n - i - 6
     ...
j(k - 1) = n - i - 3(k - 1)   such that j(k-1) >= 0 
    j(k) = n - i - 3k         such that   j(k) < 0

寻找 k 涉及解决不等式 n - 1 - 3k < 0。为了方便起见，让我们 "ignore" 事实上 k 是一个整数，我们需要取下面结果的整数部分。

n - i - 3k < 0 <=> k = (n - i) / 3

所以有(n - i) / 3"steps"需要考虑。通过步骤，我们在这里指的是循环条件的评估次数。 j <- j - 3操作的执行次数为后者减一

所以我们找到了 G(n, i) 的表达式：

G(n, i) = (n - i) / 3

现在让我们回到我们在（3）中找到的T(n)的表达式：

T(n) = sum(k = 0, k < n, (n - k) / 3)

因为当k从0变化到n，n - k从n变化到0，我们可以等价地把T(n)写成：

T(n) = sum(k = 0, k <= n, k / 3)
     = (1/3).sum(k = 0, j <= n, k)
     = (1/6).n.(n+1)

因此您可以得出结论

T(n) = Theta(n^2)

此决议展示了一些模式，您可以根据这些模式创建自己的食谱来解决类似的练习：

考虑各个级别的操作数（一次一个循环）并为表示它们的函数引入符号；
找出这些函数之间的关系；
找出最内层函数的代数表达式，它不依赖于你引入的其他函数，并且可以从循环不变量计算步数；
使用这些函数之间的关系，找到堆栈中更高层函数的表达式。

根据 Big theta 分析时间复杂度

Analyse time complexity in terms of Big theta

complexity-theory