c++ - 理解算法的复杂性

Question

我正在看一些编码面试的在线算法解决方案，我不明白为什么这个算法声称是 O(n^3)。

Caveat: I understand that big-Oh notation is abused in industry, and when I refer to O(n), I'm using that notation to mean the upper bound of an algorithms runtime as is common outside of academia in most places.

寻找最长的回文子串。一个简单的解决方案可能是:

bool isPalindrome(std::string s) {
  if (s.length() <= 1) {
    return true;
  }

  if (s[0] == s[s.length() - 1]) {
    return isPalindrome(s.substr(1, s.length() - 2));
  } else {
    return false;
  }
}

std::string longestPalindrome(std::string s) {
  std::string max_pal = "";
  for (size_t i = 0; i < s.length(); ++i) {
    for (size_t len = 1; len <= s.length() - i; ++len) {
      std::string sub = s.substr(i,len);
      if (isPalindrome(sub)) {
        if (max_pal.size() < sub.size()) max_pal = sub;
      }
    }
  }
  return max_pal;
}

这个算法不是O(n^2)吗？很简单，生成所有子串需要O(n^2)的时间，判断是否回文需要O(n)的时间。其中 n 是初始字符串中的字符数。

Answer 1

Isn't this algorithm O(n^2)? Very simply, it takes O(n^2) time to generate all substrings, and O(n) time to determine if it's a palindrome.

您所描述的恰好是 O(n^3)，因为对于每个子字符串，您正在执行一个成本为 O(n) 的操作，因此总数操作是 O(n^2 * C*n)，也就是 O(n^3)

---

但是，描述的代码其实是O(n^4)，isPalindrome()是O(n^2 ):

• 您正在创建 O(n) 个子字符串，大小为:1 + 3 + 5 + ... + n-2，即 O( n^2) 总时间。
• 在 longestPalindrome() 中执行此 O(n^2) 次总计为 O(n^4)。

(假设 O(n) substr() 复杂性。它没有定义 - 但 it's usually the case )