时间复杂度——多变量分析运行时

Question

假设我们有一个函数，其运行时间可以用以下等式表示：

T = mn - m^2 + m（其中 m 和 n 是函数的输入）

如果变量是……，我们将如何使用大 O 符号分析（最坏情况）这个运行时？ 一）独立？ b) 依赖使得 m <= n for all valid inputs?

也就是说，在这两种情况下，我们如何使用大 O 符号来简化运行时方程？

a) 我的分析基于我从华盛顿大学找到的 讲义。简而言之，如果输入变量是独立的，那么我们必须分别考虑并保留在 m 较大和 n 较大时占主导地位的项：

当 m 很大时，第二项 (-m^2) 增长最快，因此，我们将保留这项。当 n 很大时，第一项 (nm) 增长最快，因此，我们将保留此项。所以，因为没有常数，O(nm-m^2).

b) 相反，当变量依赖时，我找不到有助于解释运行时分析的资源（将不胜感激），所以我以我能做的最好的方式对其进行了合理化......

如前所述，假设m <= n for all valid inputs of the function. We will again consider our two cases:

当 m 很大时，n 也一样大或更大（给定上面的关系）。结果，nm的值将大于或等于-m^2的绝对值，即nm占优势。

当n很大时，m可以取小于等于n的任意值。因此，nm 将大于或等于-m^2 的绝对值，这意味着 nm 占主导地位。

所以，因为没有常数，O(nm)。

我对第二个大 O 符号的唯一抱怨是它具有误导性。此外，这意味着给定函数的运行时间与 nm 直接相关。因此，随着 nm 的增加，运行时间也应该增加。

假设，假设 n = 5 和 m = 3.

如果我们使用我们原来的运行时间方程，T = nm - m^2 + m = 5(3) - 3(3) + 3 = 9.

现在，假设 n = 5 和 m = 5.

根据我们的大 O 表示法，由于 nm 等于 15，现在等于 25，因此运行时间应该会相应增加。然而，运行时间实际上减少了：

T = (5)(5) - (5)(5) + 3 = 3.

我的分析正确吗？如果没有，我该怎么办？

Answer 1

如果您在

m

公式中分解

T = mn - m^2 + m

，您将得到

T = m(n+1-m)

，这表明

n

必须大于或等于

m-1

，否则您将得到零处理时间或负时间。鉴于此，

n

的大小将始终影响总处理时间，它应该保持在时间复杂度内。 m 等于 n 的情况是轶事，与整体复杂性无关。

在这种情况下，

n

和

m

实际上是独立的（因为你不能根据另一个计算一个）。您可以将复杂度表示为

O(mk)

，其中

k

是

m

和

n

之间的距离。像这样表达，你会得到两个完全独立增长的参数。如果它的参数是

m

和

k

而不是

m

和

m+k

，那么您的函数将是相同的。

Answer 2

Bravo，你的分析是正确的。 在场景（a）中，主导项是-m^2，当m很大时，而当n很大时是nm。 O(nm - m^2).

的大 O 符号

关于第二种情况，您正确地确定了（因为 m <= n）主导项始终是 nm，无论 m 还是 n 更大。然后是O(nm).
的大O符号 n 的大小总是会影响总的处理时间，因此，它应该包括在时间复杂度分析中（随着 n 的增加，处理时间也会增加）。
在 m 等于 n 的例外情况下，即使 nm 增加，运行时间也会减少。 但是，它与整体时间复杂度分析无关，因为它不会影响大多数输入的函数的一般行为。

这个例子演示了为什么大 O 表示法是渐近上限，而不是运行时的精确表示。 O(nm) 是最坏情况下运行时间的界限，但它没有告诉我们任何关于特定输入的确切运行时间。