理解算法的复杂性

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)总时间.
• O(n^2)按longestPalindrome()总计执行此操作O(n^4).

(这假设O(n) substr()复杂性.它没有定义 - 但通常是这种情况)