1

我正在为我的 Facebook 面试学习一些代码。我理解这个算法的作用，但我无法弄清楚它的复杂性。这是我访问过的网站上所说的：

由于围绕中心展开回文可能需要 O(N) 时间，因此总体复杂度为 O(N^2)。

有人可以向我解释他们是如何获得运行时间的，特别是平均情况和最差情况吗？

给出的问题是找到最大的回文子串。我对字符串有点陌生。

我也想知道你们是否认为我应该学习 Manacher 算法，即 O(N)。这是一个使用更少内存的更好的解决方案，但我真的很难理解。

string expandAroundCenter(string s, int c1, int c2) {
  int l = c1, r = c2;
  int n = s.length();
  while (l >= 0 && r <= n-1 && s[l] == s[r]) {
    l--;
    r++;
  }
  return s.substr(l+1, r-l-1);
}

string longestPalindromeSimple(string s) {
  int n = s.length();
  if (n == 0) return "";
  string longest = s.substr(0, 1);  // a single char itself is a palindrome
  for (int i = 0; i < n-1; i++) {
    string p1 = expandAroundCenter(s, i, i);
    if (p1.length() > longest.length())
      longest = p1;

    string p2 = expandAroundCenter(s, i, i+1);
    if (p2.length() > longest.length())
      longest = p2;
  }
  return longest;
}
4

1 回答 1

1

阅读Big O notation and Analysis of algorithm和一点点这个，然后回来看看我的其余答案是否有意义。

在继续之前，如果字符串本身是回文，我会使用 O(n) 算法进行检查。

让我们看看，你有一个运行 n 次的 for 循环，在每次迭代时，你调用一个运行的函数......好吧，最坏的可能情况是你每次调用时总是找到最长的可能回文，expandAroundCenter即迭代运行直到l < 0 || r > n-1. 这意味着该算法是O(min(i, n-i))。现在如果我们找到从 1 到 n 的和min(i, n-i)，我们得到这个，它是 O(n²)。

于 2013-09-15T17:24:44.987 回答