理解算法复杂度

Question

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

注意:我知道在工业中使用的是大-欧表示法，当我提到O(n)时，我用这个表示法来表示算法运行时的上限，这在大多数地方在学术界之外是很常见的。

找到最长的回文子串。一个简单的解决办法可能是：

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^2)时间，而确定它是否为回文则需要O(n)时间。

您所描述的正是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()中执行此longestPalindrome()时间将总计为O(n^4)。

(这假定O(n) substr()复杂性。它没有定义--但是通常都是这样)

Answer 2

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

Answer 3

O(n^2) (子字符串原来是O(n)本身)在双循环(O(n^2))中执行。这给了我们O(n^4)。