我正在查看一些关于编程面试的在线算法解决方案，但我不理解为什么这个算法被称为O(n^3)。
警告：我知道在工业界中经常滥用大O符号，当我提到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是初始字符串中字符的数量。