Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

Средний и худший случай
Оценка сложности алгоритма упорядочения является верхней границей сложности алгоритма. Если программа имеет высокий уровень сложности, это не значит, что алгоритм действительно будет выполняться долго. Для некоторых наборов данных запуск алгоритма занимает гораздо меньше времени, чем догадка, основанная на их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A. Если нужный элемент окажется в конце списка, то программе придется выполнить N шагов. В этом случае сложность алгоритма составляет O(N). В этом наихудшем случае время работы алгоритма максимально. С другой стороны, желаемый элемент может быть указан в первом случае. Алгоритму нужно выполнить только один шаг.
функция Найдите (данные: целое число): целое число;
есть:
целое число;
эт:
логический;
начинать
эт:=ложь;
я:=1;
в то время как (не fl) и (i<=N) делают
начинать
если A[i]=данные, то
fl:=true иначе
я:=я+1;
конец
если не фл то
я:=0;
Найдите: = я;
конец
Обе эти ситуации невозможны. Нас больше интересует ожидаемый вариант. Если элемент списка изначально перемешан случайным образом, то нужный элемент может появиться в любом месте списка. В среднем для нахождения нужного элемента требуется N/2 сравнений. Таким образом, сложность этого алгоритма в среднем составляет O(N/2) = O(N).
В этом случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), а ожидаемое поведение характеризуется оценкой O(N*log(N)), что значительно быстрее.


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