1

Facebookのインタビュー用にいくつかのコードを勉強しています。このアルゴリズムの機能は理解できますが、その複雑さがわかりません。これは私が訪問したウェブサイトに記載されているものです：

回文を中心に展開すると O(N) の時間がかかるため、全体の複雑さは O(N^2) になります。

具体的には、平均的なケースと最悪のケースで、その実行時間をどのように取得したかを誰か説明してもらえますか?

与えられた問題は、最大の回文部分文字列を見つけることです。私は文字列が初めてです。

また、O(N) である Manacher のアルゴリズムを学ぶ必要があると考えているかどうかも知りたいです。メモリの使用量が少ないより良い解決策ですが、私には理解するのが本当に難しいです。

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表記法とアルゴリズムの分析、およびこれを少し読んでから、戻ってきて、私の答えの残りの部分が意味をなすかどうかを確認してください。

先に進む前に、文字列自体が回文であるかどうかを O(n) アルゴリズムで確認します。

見てみましょう、n 回実行される for ループがあり、各反復で、実行される関数を呼び出します...まあ、最悪の場合は、呼び出すたびに可能な限り最長の回文を常に見つけることです。expandAroundCenterつまり、反復が実行されるまでl < 0 || r > n-1. これは、アルゴリズムが であることを意味しますO(min(i, n-i))。の 1 から n までの合計を求めると、O(n²) の がmin(i, n-i)得られます。

于 2013-09-15T17:24:44.987 に答える