Какова временная сложность алгоритма, который всегда занимает одинаковое время выполнения, независимо от размера входных данных?
O(1) представляет собой постоянную временную сложность. Это означает, что алгоритм всегда занимает одинаковое время выполнения, независимо от размера входных данных.
Какова временная сложность вычисления длины односвязного списка, если длина не хранится отдельно?
Если счётчик длины не хранится, чтобы вычислить длину односвязного списка, необходимо пройти каждый узел от головы до хвоста, что приводит к временной сложности O(n).
Какой жадный алгоритм находит кратчайшие пути от одной вершины в графе с неотрицательными весами, выбирая следующую вершину через очередь с приоритетом?
Алгоритм Дейкстры часто применяется для нахождения кратчайшего пути в графах с неотрицательными весами ребер. Он использует приоритетную очередь для эффективного определения минимального расстояния.
Какой набор содержит примеры самобалансирующихся двоичных поисковых деревьев?
AVL‑деревья и красно‑черные деревья являются типами самобалансирующихся деревьев, которые гарантируют, что дерево остаётся сбалансированным после каждой вставки или удаления.
Что необходимо определить в рекурсивной функции, чтобы предотвратить бесконечную рекурсию?
Базовый случай необходим в рекурсивной функции, чтобы остановить рекурсивные вызовы, когда выполнено определённое условие, предотвращая бесконечную рекурсию.
Какова временная сложность наивной рекурсивной реализации последовательности Фибоначчи?
Наивная рекурсивная реализация последовательности Фибоначчи имеет временную сложность O(2^n) из‑за обширных повторных вычислений для каждого числа Фибоначчи.
Какая структура данных обычно используется для реализации приоритетной очереди?
Приоритетная очередь обычно реализуется с помощью кучи, потому что она обеспечивает эффективное извлечение элемента с наивысшим или наименьшим приоритетом.
Какой набор перечисляет общие порядки обхода в глубину для бинарного дерева?
In-order, Pre-order и Post-order — это три распространённых порядка обхода в глубину для бинарных деревьев, каждый из которых отличается порядком посещения узлов. Обход в ширину также распространён, но относится к другой категории обходов.
Устойчива ли стандартная пузырьковая сортировка, которая меняет соседние элементы местами только когда левый строго больше правого?
Такая пузырьковая сортировка устойчива: элементы с равными ключами не меняются местами и сохраняют относительный порядок. Вариант, меняющий местами равные элементы, может нарушить устойчивость.
