algorithm - 具有两个不同参数的嵌套循环的时间复杂度

Question

如何计算这个算法的时间复杂度，包括 O() 和 Ω()。

这个嵌套循环不同于常见的嵌套循环分析，因为m和n是独立的使得|A| = n ≥ |B| =米。

我的想法是每次迭代都会运行 O(1) 时间。

对于迭代的次数(第3行和第4行)，应该是

m + (m − 1) + ... + 1 + (n - m) = O(m^2 + n)

因此，该算法的时间应该是O(m^2 + n)，Ω也是。

但是，解决方案告诉我它应该是 O(mn) 和 Ω(mn)。我不知道如何得到那个答案。

Answer 1

Can Berk Güder 的简洁解释

O denotes an upper bound, but this bound might or might not be tight.

Ω denotes a lower bound, but this bound might or might not be tight.

在您的情况下，我们不考虑将存在的特定值(可能的循环)，但仅从数学角度来看，它是 O(mn) 和 Ω(mn) 因为有一个 n 外循环和 m 内循环。

在 wiki 中有一个更直接的定义或许可以进一步阐明您的难题。

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size).