Бинарный поиск: Логарифмическая сложность
Логарифмическая сложность (O(logn)) - хорошая сложность, уступающая разве что O(1).
Наглядно рассмотрим, как растет количество операций с увеличением входных данных. Рассмотрим логарифмическую (O(logn)) и линейную (O(n)) сложности.
Вспоминаем задачу. Поиск числа в массиве из 100 элементов:
O(logn) = 7
Почему 7? Существует 100 элементов. 2⁶ = 64 (не хватает), 2⁷ = 128 (рассматриваем худший случай).
O(n) = 100 (Перебор. Худший случай - загадали число 100)
ВАЖНО!
НЕЛЬЗЯ сравнивать асимптотики и говорить, что O(logn) в 14 раз (100 / 7) быстрее O(n).
Рассмотрим увеличение входных данных:
1000 элементов
O(logn) = 10 (2¹⁰ = 1024)
O(n) = 1000
10000 элементов
O(logn) = 14 (2¹⁴ = 16384)
O(n) = 10000
Как вы видите, O(logn) растет очень медленно.
___
Убедимся, что сравнивать асимптотики между собой нельзя:
100 элементов
100 / 7 = 14 (Получается будто O(logn) в 14 раз быстрее O(n))
1000 элементов
1000 / 10 = 100 (Получается будто O(logn) в 100 раз быстрее O(n))
10000 элементов
10000 / 14 = 714 (Получается будто O(logn) в 714 раз быстрее O(n))
___
course_intro
