2. Основы алгоритмов Flashcards
Какая наилучшая сложность может быть у функции, капитализирующей первый символ в строке?
O(N) — строки в C# менять нельзя, поэтому придется создать новую, скопировав символы исходной
Какие известные вам структуры данных позволяют получить значение по ключу за O(1)?
Array, List, Dictionary, Hashtable
Как можно посчитать сумму элементов массива без циклов и библиотечных функций?
С помощью рекурсии. Сумма пустого массива — 0. Сумма непустого — это первый элемент + сумма оставшейся части массива.
Сортировка пузырьком. Опишите идею, временную и ёмкостную сложность алгоритма.
Последовательно каждое значение в массиве передвигается к началу (всплывает) до нужной позиции. Временная сложность O(n²), ёмкостная — O(1)
Сортировка слиянием. Опишите идею, временную и ёмкостную сложность алгоритма.
Массив разбивается на две примерно равные части, каждая сортируется этим же алгоритмом, затем отсортированные части объединяются. Временная сложность O(n log n). Емкостная — O(n)
Быстрая сортировка. Опишите идею, временную и ёмкостную сложность алгоритма.
Выбирается элемент разделитель, после чего элементы массива переставляются так, чтобы слева оказались элементы меньшие разделителя, а справа большие. Дальше на каждой из двух частей вызываем сортировку рекурсивно. Временная сложность O(n²), но в среднем случае O(n log n). Ёмкостная — O(n) на хранение данных на стеке при рекурсивных вызовах.
Можно ли найти элемент в отсортированном массиве быстрее, чем за линейный просмотр?
Да, с помощью бинарного поиска.
Идея и временная сложность бинарного поиска
Сравнивать элемент из середины массива с искомым и в зависимости от результата сравнения искать в левой или правой половине массива. Временная сложность O(log n)
Дайте определение временной сложности алгоритма
Это функция, которая размеру входных данных ставит в соответствие точную верхнюю грань количества элементарных операций, которое требуется алгоритму на входах заданного размера.
Дайте определение ёмкостной сложности алгоритма
Это функция, которая размеру входных данных ставит в соответствие точную верхнюю грань количества дополнительной памяти, которое требуется алгоритму на входах заданного размера.
Почему быстрая сортировка называется быстрой?
Несмотря на то, что ее сложность O(n²), в среднем она работает быстрее, чем сортировка слиянием и многие другие сортировки.
Зачем нужна O-нотация для описания временной сложности алгоритма?
“Количество элементарных операций” в определении сложности в реальности очень условное понятие. Процессоры устроены сложно и даже одна и та же операция может иметь разную стоимость в зависимости от ситуации. Поэтому точное значение сложности не имеет смысла, а проще работать с оценкой сложности.
Чем Θ(n) отличается от O(n)?
Θ — это точная оценка асимптотики, а O — лишь оценка сверху.
Какова сложность добавления элемента в начало List?
O(n). List реализован поверх массива. Для вставки нового элемента в начало, придется сдвинуть вправо все элементы List на одну позицию.
