Сложность базовых операций структур данных

В заключение данной лекции, оценим вычислительную сложность операций ранее рассмотренных базовых структур данных без детальных пояснений.

Операции с векторами характеризуются следующей вычислительной сложностью:

Вставка в конец вектора оценивается как амортизированная константная вычислительная сложность. Предсказать ее строго аналитически является нетривиальной задачей. Проблема состоит в том, что вектор может в некоторый момент времени достигнуть размера выделенного блока целиком, вызвав процедуру удвоения с переносом данных в новый блок. До момента роста вычислительная сложность не зависит от размера и является константной O(1). При больших N рост вектора происходит довольно редко, однако в этот редкий момент сложность равна O(N).

Понятие амортизированной сложности можно легко представить на жизненном примере. Предположим, 1 пачка бумаги из 500 листов стоит 40 грн, и бумага продается только целыми пачками. Какова стоимость одного листа бумаги? Наивная логика состоит в делении стоимости пачки на количество листов:

40500=0,08 грн.

Рассуждая формально, в ситуации, когда бумага закончилась, первый лист бумаги будет стоить 40 грн., поскольку купить меньше целой пачки не представляется возможным. После покупки пачки остальные 499 листов “достанутся” бесплатно. Хотя этот вывод вызывает улыбку у многих людей, это соответствует истине. Конечно, если использовать все 500 листов из купленной пачки, то их средняя стоимость составит 8 коп., исходя из приведенной выше формулы.

Точно также, вставка элемента в конец вектора, вызывающая его рост, будет иметь высокую стоимость, в то время как вставки следующих элементов, не вызывающих рост будут практически мгновенными. Таким образом, амортизированная вычислительная сложность - это среднее арифметическле от сложности обработки достаточно большого количества элементов.

Аналогично, вставка элемента в произвольную позицию вектора, также может привести к его росту, поэтому будем считать ее амортизированной линейной.

Операции со связными списками ведут себя более предсказуемо:

Связный список заметно привлекательнее при вставке/удалении элементов в произвольной позиции, т.к. это сводится к переназначению связей. В то же время, очевиден проигрыш при определении количества элементов и доступе к i-ой ячейке.

Очереди, реализованные на основе циклического массива фиксированного размера, будут демонстрировать константную вычислительную сложность всех операций. Это очевидно лишь глядя на код реализации, не содержащий ни одного цикла.

Поиск в отображениях и множествах, реализованных на основе массивов или списков характеризуется линейной сложностью. Теоретико-множественные операции (объединение, пересечение, разность) без предварительной сортировки данных в базовых структурах будут обладать квадратичной сложностью, т.к потребуется сравнение каждого элемента с каждым.

Выводы

В данной лекции было введено понятие вычислительной сложности алгоритмов. Была показана ее роль как определяющего фактора, влияющего на быстродействие решения задач. С иллюстративными примерами были перечислены типичные случаи функций, описывающих вычислительную сложность, показаны поверхностные, эмпирические и аналитические способы оценки. Особое внимание было уделено сравнению алгоритмов линейного и бинарного поиска, а также целому семейству классических алгоритмов сортировки. Прочувствовав важность оценки вычислительной сложности, программист должен осознанно подходить к выбору алгоритма для решения задачи.