如果 m <= n，时间复杂度 O(nm) 是否等于 O(n^2)
Is time Complexity O(nm) equal to O(n^2) if m <= n
我正在研究一种算法的时间复杂度，以查找字符串 n 是否包含子字符串 m，其中 m <= n。分析的结果是时间复杂度为O(nm)。所以以这个时间复杂度为起点，知道m <= n，因此mn <= n^2。我们可以说大 O 表示法的时间复杂度是 O(n^2).
确实是这样，如果一个函数的运行时间是O(mn)，并且你知道m≤n这个事实，那么这个函数的运行时间就是O(n2).
但是，这可能不是表征运行时的最佳方式。如果 m 是一个可调参数，范围可以从 0 到 n，那么 O(mn) 可能是表征运行时的 "better" 方式。例如，假设这是一个从 n 元素数组中找出 m 个最小元素的算法。如果要使用此算法从千万个（n = 106）中找出前五个元素（m = 5），则将运行时间表征为 O(n2) 会大大高估实际完成的工作量，而 O(mn) 会更好地限制运行时间。
在字符串搜索的情况下，两个字符串的长度可能截然不同这一事实是将运行时间描述为 O(mn) 的一个很好的理由，因为它向您展示了运行时间如何随两个字符串的运行时间扩展输入字符串的数量，而不仅仅是其中一个字符串。
希望对您有所帮助！
我正在研究一种算法的时间复杂度，以查找字符串 n 是否包含子字符串 m，其中 m <= n。分析的结果是时间复杂度为O(nm)。所以以这个时间复杂度为起点，知道m <= n，因此mn <= n^2。我们可以说大 O 表示法的时间复杂度是 O(n^2).
确实是这样，如果一个函数的运行时间是O(mn)，并且你知道m≤n这个事实，那么这个函数的运行时间就是O(n2).
但是，这可能不是表征运行时的最佳方式。如果 m 是一个可调参数，范围可以从 0 到 n，那么 O(mn) 可能是表征运行时的 "better" 方式。例如，假设这是一个从 n 元素数组中找出 m 个最小元素的算法。如果要使用此算法从千万个（n = 106）中找出前五个元素（m = 5），则将运行时间表征为 O(n2) 会大大高估实际完成的工作量，而 O(mn) 会更好地限制运行时间。
在字符串搜索的情况下，两个字符串的长度可能截然不同这一事实是将运行时间描述为 O(mn) 的一个很好的理由，因为它向您展示了运行时间如何随两个字符串的运行时间扩展输入字符串的数量，而不仅仅是其中一个字符串。
希望对您有所帮助！