algorithm - 为什么暴力算法的时间复杂度是 O(n*m)？

Question

我正在使用以下强力算法在另一个字符串中搜索一个字符串。

据我所知，在最坏的情况下，比较次数是 (n-m+1)*m，但时间复杂度的正确答案应该是 O(n *m).

为了得到这个答案，我进行了以下转换:

(n-m+1)*m = (n+1) * m - m^2 = O(n*m) - m^2

如何从这里得到O(n*m)？

-m^2 去哪儿了？

蛮力算法:

NAIVE-STRING-MATCHER

n = T.length
m = P.length
for s = 0 to n - m
    if P[1...m] == T[s+1...s+m]
        print s

Answer 1

运行时间确实属于O(m(n-m))。但由于 Big-O 符号是上界，这也是 O(mn)，因为 mn ≥ m(n-m)。

在实践中，这种简化并没有什么害处，因为您通常希望搜索字符串的长度与模式的长度成正比。然后 m = αn 产生 m(n-m) = mn(1-α)。