如果 m <= n，时间复杂度 O(nm) 等于 O(n^2)

Question

我正在研究算法的时间复杂度，以查找字符串n是否包含子字符串m（其中m <= n ）。分析结果是时间复杂度为O(nm)。因此，以这个时间复杂度为起点，并知道m <= n，因此mn <= n^2。我们可以说大 O 表示法的时间复杂度是O(n^2)吗？

Answer 1

确实如此，如果函数的运行时间为 O(mn) 并且您知道 m ≤ n，则该函数的运行时间为 O(n ² )。

然而，这可能不是表征运行时的最佳方式。如果 m 是一个可调参数，范围可以是 0 到 n，那么 O(mn) 可能是描述运行时间的“更好”方式。例如，假设这是一个从 n 元素数组中查找 m 个最小元素的算法。如果要使用此算法从一千万个 (n = 10 ⁶ ) 中查找前五个元素 (m = 5)，则将运行时间描述为 O(n ² ) 会大大高估实际完成的工作量，而O(mn) 会给运行时间带来更好的限制。

在字符串搜索的情况下，两个字符串的长度可能相差很大，这是将运行时间描述为 O(mn) 的一个很好的理由，因为它向您展示了运行时间如何随两个输入字符串的运行时间进行缩放，不仅仅是一根弦。

希望这可以帮助！