algorithm - 分析复制算法的最佳运行时间

Question

我不知道如何计算此算法的最佳运行时间 - omega f(n)。特别是，我不明白怎么会有“最佳情况”——这似乎是一个非常简单的算法。有人可以给我一些提示/解决此类问题的一般方法吗？

for i = 0 to n do
    for j = n to 0 do
        for k = 1 to j-i do
            print (k)

Answer 1

看看这个问题和答案 Still sort of confused about Big O notation它可能会帮助您理清最坏情况、最佳情况、Big O、Big Omega 等之间的一些混淆。

至于你的具体问题，你被要求找到算法时间复杂度的一些(渐近)下界(你还应该澄清你是指大欧米茄还是小欧米茄)。

否则你是对的，这个问题很简单。您只需要考虑对于给定的 n 将执行多少次 print (k)。

您可以看到第一个循环进行了 n 次。第二个也是n次。

对于第三个，你看到如果i = 1，那么j = n-1，因此k是1到n-1-1 = n-2，这让我想你的例子是否正确，如果有应该是i-j。

无论如何，第三个循环至少会执行n/2次。它是 n/2 因为你减去 j-i 并且 j 减少而 i 增加所以当它们是 n/2 结果将是 0 然后它将为负，此时最内层循环将不再执行。

因此 print (k) 将执行 n*n*n/2 次，即 Omega(n^3) 您可以很容易地从定义中验证。

请注意，正如@Yves 在他的回答中指出的那样，这一切都假设 print(k) 是在恒定时间内完成的，这可能就是您练习中的意思。

在现实世界中，这不是真的，因为打印数字也需要时间，如果 print(k) 打印，时间会随着 log(n) 的增加而增加在基数 2 或基数 10 中(基数 1 为 n)。

否则，在这种情况下，最好的情况与最坏的情况相同。只有一个大小为 n 的输入，因此您无法找到大小为 n 的“最佳实例”和大小为 n 的“最差实例”。只有大小为 n 的实例。