Перевод статьи «Big O Notation Examples – Time Complexity and Algorithm Efficiency Explained».
Анализ временной сложности помогает нам определять, насколько больше времени потребуется нашему алгоритму для решения более объемной задачи.
В этой статье я расскажу о значении нотации «О» большое в анализе временной сложности. Мы рассмотрим три примера алгоритмов проверки чисел на простоту. А для анализа временной сложности этих алгоритмов мы будем использовать нотацию «О» большое.
Что такое нотация «О» большое?
Нотация «О» большое описывает, как возрастает предположительное время работы алгоритма по мере увеличения размера решаемой задачи.
Давайте рассмотрим некие гипотетические алгоритмы для сортировки списка чисел.
1. Допустим, у нас есть алгоритм сортировки с временной сложностью O(n). Это значит, что по мере увеличения списка чисел время работы этого алгоритма возрастает линейно.
Список, содержащий в 10 раз больше элементов, будет обрабатываться в 10 раз дольше. Таким образом, если сортировка 10 чисел занимает 4 секунды, мы можем рассчитывать, что сортировка 100 чисел займет приблизительно 40 секунд.
2. Если же наш алгоритм сортировки имеет временную сложность O(n²), время его работы при увеличении количества элементов в списке будет расти не линейно, а квадратично.
Список, содержащий в 10 раз больше элементов, будет обрабатываться примерно в 100 раз дольше! Это означает, что если сортировка 10 чисел занимает 4 секунды, то сортировка 100 чисел займет около 400 секунд.
3. Самые быстрые алгоритмы для сортировки списка имеют временную сложность O(n log(n)). Применяя их, мы можем рассчитывать, что в 10 раз больший список будет обрабатываться примерно в 23 раза дольше.
Иными словами, если сортировка 10 чисел занимает 4 секунды, сортировка 100 чисел займет примерно 92 секунды.
Пример использования нотации «О» большое. Проверка на простоту
Теперь, зная, о чем говорит нотация «О» большое, давайте посмотрим, как мы можем использовать ее в анализе временной сложности.
В этом разделе мы рассмотрим три разных алгоритма проверки чисел на простоту. Исходя из определения простых чисел, число num считается простым, если делится без остатка только на 1 и на num.
Алгоритм 1. Проверяем все возможные делители
Самый простой способ проверки числа на простоту, который я могу придумать, — это проверить, есть ли для этого числа еще какие-нибудь делители, кроме него самого и 1.
В функции is_prime_all() я пробую разделить num на каждое число в диапазоне между 1 и num и проверить, есть ли остаток.
Этот код я написал на Rust, чтобы иметь возможность использовать criterion для замера времени работы. Но анализ временной сложности с применением нотации «О» большое работает одинаково с любым языком программирования.
Если хотите запустить criterion с этим кодом на своем компьютере, исходный код на Rust можно взять на GitHub.
pub fn is_prime_all(num: i64) -> bool {
// Check for divisors of num
for i in 2..num {
if num % i == 0 {
// Any divisor other than 1 or num means num is not prime
return false;
}
}
// No other divisors found means num is prime
return true;
}
Чтобы точно определить, является ли число num простым, нам нужно проверить num - 2 чисел. Поэтому временная сложность этого алгоритма — O(num) или O(n).
Как вы заметили, мы убрали из нотации -2. При вычислении временной сложности алгоритма в нотации «О» большое мы учитываем только самый значительный фактор в уравнении, а более мелкие детали просто опускаются.
Когда я протестировал свою функцию, моему компьютеру потребовалось 5,9 микросекунды, чтобы проверить, является ли число 1789 простым. А чтобы проверить число 17903, нужно было в среднем 60 микросекунд.
Это означает, что для проверки в 10 раз большего числа требуется приблизительно в 10 раз больше времени — как и предсказывал наш анализ временной сложности!
Алгоритм 2. Проверяем половину возможных делителей
Наш алгоритм можно улучшить. Если наше число num не делится на 2, мы можем заключить, что оно не делится и на num/2, и на все числа, большие num/2. Это значит, что мы можем проверять меньшее количество чисел:
pub fn is_prime_half(num: i64) -> bool {
// Check for divisors of num
for i in 2..num / 2 {
if num % i == 0 {
// Any divisor other than 1 or num means num is not prime
return false;
}
}
// No other divisors found means num is prime
return true;
}
Работа этого кода занимает в два раза меньше времени. На моем компьютере для проверки того, является ли число 1789 простым, потребовалось только 3,1 микросекунды. К сожалению, чтобы проверить число 17903, потребовалось 31,1 микросекунды. Это означает, что временная сложность нашего алгоритма не изменилась!
Дело в том, что самый значительный фактор — num — остался прежним. Нам нужно проверить num/2 - 1 значений, то есть временная сложность все равно O(n).
Алгоритм 3. Проверяем все возможные пары делителей
Давайте попробуем применить третий алгоритм. Посмотрим, сможем ли мы достичь меньшей временной сложности.
Наш второй алгоритм строился на основе того факта, что если число не делится на 2, то и на num/2 оно тоже не делится.
Но это работает не только с двойкой. Если наше число не делится на 3, то оно не делится и на num/3. Если не делится на 4, то не делится и на num/4.
Самое большое число, которое нам нужно проверить, это корень квадратный из num, потому что √num * √num = num.
pub fn is_prime_sqrt(num: i64) -> bool {
// Check for divisors of num
for i in 2..=(num as f64).sqrt() as i64 {
if num % i == 0 {
// Any divisor other than 1 or num means num is not prime
return false;
}
}
// No other divisors found means num is prime
return true;
}
Мы проверяем лишь √num - 1 различных чисел, значит, временная сложность должна быть O(√n). При запуске на моем компьютере проверка числа 1789 заняла 161,9 наносекунды, а проверка числа 17903 — 555 наносекунд.
То есть проверка в 10 раз большего числа заняла примерно в 3,4 раза больше времени, а √10 ≈ 3,2. Наш анализ временной сложности позволил точно оценить, сколько времени будет длиться работа нашего алгоритма при проверке большего числа.
Итоги
Анализ временной сложности помогает нам определять, насколько больше времени потребуется алгоритму, чтобы решить такую же задачу, но большего масштаба.
Мы разобрали, что означает нотация «О» большое при анализе временной сложности и использовали эту нотацию на практике для оценки трех алгоритмов.
[customscript]techrocks_custom_after_post_html[/customscript]
[customscript]techrocks_custom_script[/customscript]