Алгоритмы Flashcards
Что такое Big O?
Big O нотация - это способ оценки скорости роста или производительности алгоритма. Она используется для определения того, насколько быстро увеличивается время выполнения программы или объем занимаемой памяти по мере увеличения входных данны.
Как происходит оценка асимптоматической сложности?
Оценка асимптотической сложности алгоритма, как правило, происходит путем анализа того, как изменяется его производительность или использование памяти при увеличении размера входных данных.
Есть несколько типичных видов асимптотических сложностей, которые обычно рассматриваются:
O(1): постоянная сложность. Время выполнения алгоритма остается постоянным независимо от размера входных данных.
O(log n): логарифмическая сложность. Время выполнения алгоритма растет логарифмически по мере увеличения размера входных данных.
O(n): линейная сложность. Время выполнения алгоритма пропорционально размеру входных данных.
O(n log n): сложность, которая увеличивается пропорционально произведению размера входных данных и логарифма этого размера.
O(n^2), O(n^3) и т. д.: квадратичная, кубическая сложности и т. д. Время выполнения алгоритма увеличивается пропорционально квадрату, кубу и так далее размера входных данных.
O(2^n): экспоненциальная сложность. Время выполнения алгоритма растет экспоненциально по мере увеличения размера входных данных.
Для оценки асимптотической сложности алгоритма обычно анализируют его основные шаги, циклы, рекурсивные вызовы и операции, определяя, как их количество или частота изменяются с увеличением размера входных данных. Затем определяют доминирующий фактор, который определяет, какой тип сложности будет преобладать в конечном итоге.
Что такое рекурсия?
это техника, при которой метод вызывает сам себя для решения задачи Ключевые аспекты рекурсии:
Базовый случай (Base Case): Это условие, при котором рекурсия завершается, и функция больше не вызывает саму себя. В приведенном примере базовый случай - это когда n равно 0 или 1, и функция возвращает 1.
Шаг рекурсии (Recursive Step): Это шаг, который сводит задачу к базовому случаю путем вызова функции с другими аргументами. В приведенном примере шаг рекурсии - это return n * factorial(n - 1);, который вызывает factorial с аргументом n - 1.
При написании рекурсивных функций важно убедиться, что базовый случай корректно обрабатывается и что каждый шаг рекурсии приближает к базовому случаю. Это поможет избежать зацикливания и обеспечит корректное завершение выполнения функции.
Сравнените преимущества и недостатки итеративных и рекурсивных алгоритмов. С примерами.
Итеративные алгоритмы и рекурсивные алгоритмы имеют свои преимущества и недостатки, и выбор между ними может зависеть от конкретной задачи, читаемости кода, производительности и других факторов.
Преимущества итеративных алгоритмов:
Простота понимания: Итеративные алгоритмы часто проще понять, поскольку они используют циклы или итерации для выполнения действий. Это делает их более интуитивно понятными для многих программистов.
Эффективность использования памяти: Обычно итеративные алгоритмы могут требовать меньше памяти, поскольку они не используют стек вызовов для хранения промежуточных значений.
Преимущества рекурсивных алгоритмов:
Понятность кода: Рекурсивные алгоритмы могут лучше отражать логику задачи и делать код более читаемым, особенно для задач, где рекурсивная структура является естественной.
Простота решения некоторых задач: Некоторые задачи естественно и эффективно решаются с использованием рекурсии, например, обход деревьев или графов.
Что такое жадные алгоритмы? Приведите пример.
Жадные алгоритмы являются одной из 3х техник создания алгоритмов, вместе с принципом “Разделяй и властвуй” и динамическим программированием.
Жадный алгоритм - это алгоритм, который на каждом шагу совершает локально оптимальные решения, т.е. максимально возможное из допустимых, не учитывая предыдущие или следующие шаги. Последовательность этих локально оптимальных решений приводит (не всегда) к глобально оптимальному решению.
Т.е. задача рабивается на подзадачи, в каждой подзадаче делается оптимальное решение и, в итоге, вся задача решается оптимально. При этом важно является ли каждое локальное решение безопасным шагом. Безопасный шаг - приводящий к оптимальному решению.
К примеру, алгоритм Дейкстры нахождения кратчайшего пути в графе вполне себе жадный, потому что мы на каждом шагу ищем вершину с наименьшим весом, в которой мы еще не бывали, после чего обновляем значения других вершин. При этом можно доказать, что кратчайшие пути, найденные в вершинах, являются оптимальными.
Пример: Алгоритм Дейкстры для поиска кратчайшего пути во взвешенном графе: На каждом шаге выбирается вершина с наименьшим весом до текущей вершины и добавляется к пути.
Расскажите про пузырьковую сортировку.
Пузырьковая сортировка - это простой алгоритм сортировки, который проходит по списку несколько раз, сравнивая соседние элементы и меняя их местами, если они стоят в неправильном порядке.
Расскажите про сортировку слиянием.
Сортировка слиянием — это алгоритм сортировки, который работает на основе принципа “разделяй и властвуй”. Он разбивает массив на две части, рекурсивно сортирует каждую из половин и затем объединяет их, чтобы получить отсортированный массив.O(n log n)
Расскажите про быструю сортировку
Быстрая сортировка разделяет массив на части относительно опорного элемента, рекурсивно сортирует эти части и объединяет их. Сложность алгоритма в среднем и лучшем случае - O(n log n), но в худшем случае - O(n^2), где ‘n’ - количество элементов в массиве.
Расскажите про бинарное дерево
Бинарное дерево - это иерархическая структура данных, состоящая из узлов, каждый из которых имеет не более двух дочерних узлов (левый и правый). Узлы содержат данные и связаны направленными ребрами. Левый потомок узла содержит значение, меньшее, чем значение родительского узла, а правый потомок - значение большее. Эта структура часто используется для эффективного поиска, вставки и удаления элементов, особенно в случае, когда данные отсортированы.
Расскажите про красно - черное дерево
Красно-чёрное дерево - это разновидность самобалансирующегося двоичного дерева поиска. Каждый узел имеет цвет - красный или черный. Оно следует определенным правилам:
Каждый узел либо красный, либо черный.
Корень и конечные узлы (листья) дерева - черные.
Красный узел не может иметь красного родителя.
Все пути от узла к его листовым узлам должны иметь одинаковое количество черных узлов.
Эти правила обеспечивают, что дерево остается сбалансированным даже после вставки или удаления элементов. Благодаря этой структуре красно-чёрное дерево обеспечивает эффективные операции вставки, удаления и поиска элементов, так как высота дерева всегда ограничена, что гарантирует временную сложность операций O(log n).
Расскажите про линейный и бинарный поиск
Линейный поиск просматривает каждый элемент в последовательности, чтобы найти нужный. Эффективен для небольших наборов данных, сложность - O(n), где ‘n’ - количество элементов.
Бинарный поиск работает на отсортированных данных, делит последовательность пополам и сравнивает искомое значение с серединой. Продолжает поиск в половине, где возможно нахождение значения. Сложность - O(log n), где ‘n’ - количество элементов.
Расскажите про очередь и стек
Очередь - это структура данных, работающая по принципу FIFO (первый вошел, первый вышел). Элементы добавляются в конец очереди (enqueue), а извлекаются из начала (dequeue).
Стек - это структура данных, работающая по принципу LIFO (последний вошел, первый вышел). Элементы добавляются и извлекаются только с одного конца стека (push и pop).
Сравните сложность вставки, удаления, поиска и доступа по индексу в ArrayList и LinkedList
У ArrayList и LinkedList различные временные характеристики для различных операций из-за разницы в их внутренних структурах данных.
ArrayList:
Вставка в конец (append): O(1) в среднем, в худшем случае O(n) из-за перераспределения памяти.
Вставка/удаление в начало или середину: O(n), так как требует перемещения элементов.
Поиск/доступ по индексу: O(1), так как массив обеспечивает прямой доступ к элементам.
LinkedList:
Вставка/удаление в начало или середину: O(1), так как нет необходимости перемещать другие элементы.
Вставка/удаление в конец: O(1) при использовании указателя на последний элемент.
Поиск/доступ по индексу: O(n), так как требуется перебор элементов с начала или конца списка до нужного индекса.
Таким образом, если нужны операции вставки/удаления в начало/середину, LinkedList может быть эффективнее, но для операций доступа по индексу ArrayList работает быстрее.
