Я смотрю на некоторые онлайн-алгоритмы решения для кодирования интервью, и я не понимаю, почему этот алгоритм считается O (n ^ 3).
Предостережение: я понимаю, что нотация big-Oh злоупотребляет в промышленности, и когда я ссылаюсь на 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 — количество символов в исходной строке.
Разве этот алгоритм не 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()
сложность. Это не определено — но это обычно бывает)
Вы почти правы,
требуется O (n ^ 2) и O (n) операции для генерации строк и их проверки.
Таким образом, вам нужно O (n ^ 2) (количество строк) умножить на O (n) проверок.
Так как n ^ 2 * n = n ^ 3, общее время выполнения в O (n ^ 3).
O (n ^ 2) (сама подстрока оказывается O (n)) выполняется внутри двойного цикла (O (n ^ 2)). Это дает нам O (п ^ 4).
На самом деле это было бы даже O (N ^ 4) из-за варварства реализации.
isPalindrome
реализован таким образом, что для каждого рекурсивного вызова выделяет новая строка, которая по сути является исходной строкой с удаленными первым и последним символами. Таким образом, каждый такой вызов уже O (n).