Алгоритмы — это интересно!

Абстрактные классы, виртуальные методы и полиморфизм

В этой статье разберем ключевые инструменты для реализации полиморфизма (одного из трёх столпов ООП наряду с инкапсуляцией и наследованием) на примере языка С++ — абстрактные классы и виртуальные методы. Виртуальный метод — метод класса, который может быть переопределён в классе‑наследнике. При вызове через указатель или ссылку на базовый класс выполняется версия метода из производного класса. Как работает: Абстрактный класс — класс, который: Ключевые особенности: Создадим класс Person c полями спецификатора protected — name и age...

1 неделю назад

На канале уже выпущены две статьи про бинарный поиск и бинарные деревья. Но что же значит «Бинарный»? Давайте разберемся. «Бинарный» происходит от латинского binarius — «двойной». В информатике это означает «состоящий из двух частей» или «имеющий два варианта». Ключевые идеи: * два варианта: да/нет, 0/1, левое/правое; * выбор между двумя возможностями на каждом шаге. Бинарный поиск — алгоритм поиска элемента в отсортированном массиве, где на каждом шаге мы: 1. Смотрим на средний элемент массива. 2. Сравниваем его с искомым значением. 3. Отбрасываем половину массива (левую или правую) — в зависимости от результата сравнения. 4. Повторяем шаги 1–3 для оставшейся половины. Почему «бинарный»: на каждом шаге выбор сводится к двум вариантам: - искомое значение находится в левой половине; - искомое значение находится в правой половине. Бинарное дерево — структура данных, где каждый узел имеет: - не более двух потомков (левого и правого); - значение в узле; - ссылки на левого и правого потомка (или null, если потомка нет). Бинарное дерево поиска добавляет правило упорядоченности: * значения в левом поддереве < значения в корне; * значения в правом поддереве > значения в корне. Почему «бинарное»: у каждого узла ровно два направления для движения: - идти влево (если ищем меньшее значение); - идти вправо (если ищем большее значение). Что общего? Оба метода используют один и тот же принцип: 1. на каждом шаге выбор между двумя вариантами; 2. исключение половины возможных вариантов; 3. быстрое сужение области поиска. Таким образом, Бинарный — значит основанный на двух элементах, вариантах или состояниях. Например, мы выбираем чай или кофе :)

1 неделю назад

Строим Бинарное дерево на Python без ООП

Эта статья посвящена сразу двум темам — рекурсии и бинарному дереву. Как и всегда с помощью несложных определений и пояснений разберем, что это такое и чем может быть полезно. Рекурсия — это когда функция вызывает саму себя внутри своего тела. Это способ решения задач, которые можно разбить на более мелкие подзадачи того же типа. Аналогия: представьте зеркало, поставленное напротив другого зеркала — вы видите бесконечное отражение. В программировании мы контролируем «глубину» этого отражения. Один...

1 неделю назад

Разбор бинарного поиска

В статье Просто об асимптотической сложности во втором примере я привёл один из самых известных алгоритмов поиска — бинарный поиск. Поэтому хотел бы его разобрать просто и наглядно в отдельной статье. Бинарный поиск — это способ быстро найти нужное значение в отсортированном списке (массиве), словно «разделяя пополам» область поиска. Посмотрим на алгоритм: Есть массив из 10 элементов с пронумерованными индексами от 0 до 9. Наша задача — найти число 23 (target). Задаем границы поиска: left = 0, right = длина массива - 1 = 9...

1 неделю назад

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

Асимптотическая сложность — это способ понять, как будет меняться время работы программы, когда объём данных сильно вырастет. Обозначается нотацией Big O. Понятие часто встречается в программировании, поэтому его любят спрашивать на собеседованиях. Разберём кратко и наглядно 9 видов, начиная от самого быстрого, с примерами на Python. 1. O(1) — константное время Время выполнения не зависит от размера данных. Пример: доступ к элементу массива по индексу. В результате получим единицу. Обращение к элементу массива происходит сразу, то есть 1 раз...

2 недели назад