Работа посвящена основам теории алгоритмов, в частности, одному из её основных понятий — оценке эффективности того или иного алгоритма. Сперва будет дано формальное определение понятия временной эффективности, которое позже будет проиллюстрировано на примере алгоритмов сортировок.
Цель работы — тщательно изучить и формализовать понятие «эффективности алгоритма», а также рассмотреть одну из фундаментальных задач при изучении алгоритмов — задачу сортировки.
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
Понятие алгоритма
Алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий, при любом наборе исходных данных.
Говоря неформально, алгоритм — это любая корректно определенная вычислительная процедура, на вход которой подается некоторая величина или набор величин и результатом выполнения которой является выходная величина или набор значений.
Алгоритм можно рассматривать как инструмент, предназначенный для решения корректно поставленной вычислительной задачи. В постановке задачи в общих чертах задаются отношения между входом и выходом. В алгоритме описывается конкретная вычислительная процедура, с помощью которой удается добиться выполнения указанных отношений.
Говорят, что алгоритм корректен, если для любых входных данных результатом его работы являются корректные выходные данные. Мы говорим, что корректный решает данную вычислительную задачу. Если алгоритм некорректный, то для некоторых вводов он вообще может не завершить свою работу ил выдать неправильный ответ.
Алгоритм может быть задан на естественном языке, в виде компьютерной программы или даже воплощен в аппаратном обеспечении. Единственной требование — его спецификация должна предоставлять точное описание вычислительной процедуры, которую требуется выполнить.
