📌 Шпаргалка по асимптотике

Чтобы лучше понимать, зачем вообще нужны функции при оценке алгоритмов, на графике собраны самые часто встречающиеся типы сложности.

Хорошо видно, насколько по-разному ведут себя алгоритмы при росте объёма входных данных.

Одни — вроде O(1) и O(log n) — остаются спокойными и надёжными даже при больших объёмах.

Другие — вроде O(n!) — начинают "плавиться" уже на середине пути. И всё это, напомню, из-за пары лишних вложенных циклов.

Такое визуальное представление — простой и наглядный способ увидеть, почему мы боремся за эффективность, почему иногда стоит потратить больше времени на выбор алгоритма, чтобы потом не удивляться, почему "всё тормозит".

В прошлом видео мы рассмотрели рекурсивный метод решения задачи про поиск максимальной глубины бинарного дерева. Теперь попробуем ее решить без использования рекурсии 🥷🏻

https://youtu.be/-2vlRTy_vxY?si=qVsnAOqhie0oCRpQ

📌 Бинарный поиск — быстрый способ найти нужное

Представь, что у тебя есть список из 240 000 книг, расположенных в алфавитном порядке. Нужно найти одну конкретную.
Если идти с начала и проверять каждую — это займёт очень много времени.
А бинарный поиск позволяет находить нужную книгу за несколько шагов.

💡 Принцип работы:

- Смотрим на элемент в середине списка.
- Если искомое меньше — продолжаем поиск в левой половине, если больше — в правой.
- Повторяем, пока не найдём или не поймём, что элемента нет.

Каждый шаг сокращает количество оставшихся элементов в два раза.
Например:
100 элементов → максимум 7 шагов
4 миллиарда элементов → максимум 32 шага

⚠️ Важно: этот метод работает только с отсортированными данными. Если порядок нарушен, результат будет неправильным.