这个算法的时间复杂度（bigO）是什么？

Question

这个算法通过查找字符串来尝试找到另一个字符串。逻辑很简单，我猜。不过，我需要帮助找到它的复杂度。

int find(string mString, string lookUp)
{
    int i, z, j, m = mString.size(), n = lookUp.size(), broken = 0, st = 0;
    for(j = 0, i = 0; i < m; i++)
    {
        if(mString[i] == lookUp[j])
        {
            if(broken)
            {
                //go back and see if we're on the good path
                broken = 0;
                for(z = 0; z < j; z++)
                {
                    if(broken) break;
                    if(mString[i-z] == lookUp[j-z])
                        broken = 0;
                    else
                        broken = 1;
                }
                if(!broken) st = i - j + 1;
            }
            if(j + 1 != n)
                j++;
        }
        else
            broken = 1;
    }
    return st;
}

有人能帮忙吗？

谢谢。

- Guluto

---

你目前有什么进展？ - Femaref

目前来看，我认为最坏的情况是O(m * n)，尽管它可能只是O((m-n) * n)。我有点困惑。 - Guluto

你忘记了带有 z 的 for 循环。 - Femaref

这就是为什么我感到困惑...虽然如果我再想一想，O(m*n + n)应该是最坏情况。你的意见呢？ - Guluto

为什么你感到困惑？有什么不清楚的地方吗？（我问这个问题是因为，如果你能确定不理解的点，我们可以给予更好的帮助。） - David Weiser

Answer 1

处理大 O 和循环时，我会问自己一个问题：

每个循环最多可以运行多少次？

在你的例子中，

1.外部循环将最多运行 `m` 次。 2.内部循环将最多运行 `n` 次。 3.对于外部循环的每次迭代，内部循环将最多运行 `n` 次。

这有助于澄清您的思路吗？

- David Weiser

Answer 2

这个算法的最终复杂度是O(n^2)。

- Mushahid Hussain