Материал: Практика 2 - Алгоритмичекая сложность алгоритмов - СФ

Рисунок 2.2 - Зависимость количества операций от длины массива

Как видно из рисунка 2.2 алгоритмическая сложность находится между

O(n^2) и O(n*log(n)). Это соответствует теоретическим данным.

Вприложении А представлен листинг программы сортировки

«расческой».

6

2.2 Быстрая сортировка

Для оценки алгоритмической сложности быстрой сортировки были построены графики зависимости времени от длины массива (рисунок 2.3) и

зависимости количества операций от длины массива (рисунок 2.4).

Рисунок 2.3 - Зависимость времени от длины массива

7

Рисунок 2.4 - Зависимость количества операций от длины массива

Как видно из рисунка 2.4 алгоритмическая сложность находится между

O(n^2) и O(n*log(n)). Это соответствует теоретическим данным.

В приложении Б представлен листинг программы быстрой сортировки.

8

2.3 Сортировка «Шелла»

Для оценки алгоритмической сложности сортировки «Шелла» были построены графики зависимости времени от длины массива (рисунок 2.5) и

зависимости количества операций от длины массива (рисунок 2.6).

Рисунок 2.5 - Зависимость времени от длины массива

9

Рисунок 2.6 - Зависимость количества операций от длины массива

Как видно из рисунка 2.6 алгоритмическая сложность находится между

O(n^2) и O(n*log(n)). Это соответствует теоретическим данным.

Вприложении В представлен листинг программы сортировки «Шелла».

2.4Анализ таблицы

Втаблице 2.1 представлено время лучших и худших случаев для сортировок.

10