Глубокое понимание логарифмов во временной сложности и их роли в компьютерной науке

Бесплатный 5-дневный мини-курс: https://backtobackswe.com Попробуйте нашу полную платформу: https://backtobackswe.com/pricing 📹 Интуитивно понятные видеообъяснения 🏃 Запускайте код по мере обучения 💾 Сохраняйте прогресс ❓Новые, ранее не встречавшиеся вопросы 🔎 Получите все решения Логарифмы и логарифмическая временная сложность долгое время сбивали меня с толку, поскольку это была одна из тех страшных вещей в математике, когда видишь символ и пугаешься, что это что-то сложное. Логарифмы очень просты. На самом фундаментальном уровне логарифм задаёт нам вопрос. log(8) по основанию 2 спрашивает меня: «На сколько мне нужно возвести 2 в степень, чтобы получить 8?» Ответ: 3. 2^3 = 8 log(100) по основанию 10 спрашивает меня: «На сколько мне нужно возвести 10 в степень, чтобы получить 100?» Ответ: 2. 10^2 = 100 Это обобщает наше понимание того, что логарифм спрашивает нас... на сколько мне нужно возвести основание, чтобы получить число, по которому мы берём логарифм? Именно это и есть результат логарифмического выражения. Кроме того, если у нас есть 8 и основание логарифма 2, мы можем разделить 8 пополам 3 раза: 8 - 4 - 2 - 1, прежде чем получим 1, и мы больше не можем делить пополам. В стандартной математике предполагается, что основание — это основание 10. В информатике основание почти всегда равно 2. Мы увидим, почему. Где мы видим логарифмы в информатике: Уровни в двоичном дереве В общем случае, двоичное дерево с n узлами будет иметь как минимум 1 + floor(log_2(n)) уровней. Когда мы выполняем что-то вроде обхода дерева или добавления или удаления элементов в кучу, мы используем ограничение O(h), которое для сбалансированного двоичного дерева фактически означает O(log(n)). В асимптотике мы обойдем не более логарифма уровней, поскольку это наше хвостовое поведение. Наше асимптотическое поведение логарифмическое. Сортировка слиянием и быстрая сортировка В сортировке слиянием мы можем сократить входные данные вдвое не более чем до log(n) раз. То же самое и для быстрой сортировки. Каждый алгоритм сортировки будет выполнять примерно log(n) уровней работы, и тогда возникает вопрос, какой объем работы мы выполним на каждом из этих уровней. Двоичный поиск В двоичном поиске мы сокращаем пространство поиска вдвое при каждой операции, основываясь на некоторых предопределенных критериях поиска, которые мы определяем для сужения пространства поиска. Мы можем сократить пространство поиска вдвое не более чем до log(n) раз. Логарифм критически важен для всех этих приложений, поскольку задаваемый им вопрос — это именно то, что нас интересует. ++++++++++++++++++++++++++++++++++++++++++++++++++++ HackerRank:    / @hackerrankofficial   Тушар Рой:    / tusharroy2525   GeeksForGeeks:    / @geeksforgeeksvideos   Джарвис Джонсон:    / vsympathyv   Успех в технологиях:    / @successintech