понимание алгоритмической сложности

Я смотрю на некоторые онлайн-алгоритмы решения для кодирования интервью, и я не понимаю, почему этот алгоритм считается 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 — количество символов в исходной строке.

6

Решение

Разве этот алгоритм не 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() сложность. Это не определено — но это обычно бывает)

8

Другие решения

Вы почти правы,
требуется O (n ^ 2) и O (n) операции для генерации строк и их проверки.
Таким образом, вам нужно O (n ^ 2) (количество строк) умножить на O (n) проверок.
Так как n ^ 2 * n = n ^ 3, общее время выполнения в O (n ^ 3).

1

O (n ^ 2) (сама подстрока оказывается O (n)) выполняется внутри двойного цикла (O (n ^ 2)). Это дает нам O (п ^ 4).

1

На самом деле это было бы даже O (N ^ 4) из-за варварства реализации.

isPalindrome реализован таким образом, что для каждого рекурсивного вызова выделяет новая строка, которая по сути является исходной строкой с удаленными первым и последним символами. Таким образом, каждый такой вызов уже O (n).

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector