理解算法的复杂性

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

你几乎是对的，它需要 O(n^2) 和 O(n) 操作来生成字符串并检查它们。因此，您需要 O(n^2) （字符串数量）次 O(n) 检查。由于 n^2 * n = n^3，总运行时间在 O(n^3).

Answer 2

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）

Answer 3

O(n^2)（子字符串本身就是O(n)）在双循环（O(n^2)）内执行。这给了我们 O(n^4).

Answer 4

实际上这甚至是 O(N^4)，因为实现的野蛮。

isPalindrome 以这样的方式实现，对于每个递归调用，它分配一个新字符串，它本质上是删除了第一个和最后一个字符的源字符串.所以每个这样的调用都已经是 O(n).

理解算法的复杂性

understanding algorithmic complexity

c++

algorithm

time-complexity

big-o

asymptotic-complexity