为什么蛮力算法的时间复杂度是O(n*m)?

I am using the following brute force algorithm for searching a string inside another string.

我正在使用下面的蛮力算法在另一个字符串中搜索一个字符串。

As I know, the number of comparisons is (n-m+1)*m in the worst case, but the right answer for time complexity is supposed to be O(n*m).

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

To get this answer, I do the following transformations:

为了得到这个答案，我做了以下变换:

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

How do you get O(n*m) from here?

你怎么从这里得到O(n*m) ?

Where did -m^2 go?

- m ^ 2去了哪里?

Brute force algorithm:

蛮力算法:

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

1 个解决方案

#1

The running time indeed belongs to O(m(n-m)). But as the Big-O notation is an upper bound, this is also O(mn), as mn ≥ m(n-m).

运行时间确实属于O(m(n-m))。但随着大0符号是一个上限,这也是O(mn),mn≥m(n - m)。

In practice, no harm is done by this simplification, as you usually expect the length of the search string to be proportional to that of the pattern. Then m = αn yields m(n-m) = mn(1-α).

在实践中，这种简化不会造成任何危害，因为您通常期望搜索字符串的长度与模式的长度成正比。然后m =αn收益率m(n - m)= mn(1-α)。

#1