ВУЗ:
нут конец списка. В самом лучшем случае каждый опорный элемент уже находится на положенном ему месте. Следователь-
но, чтобы это было обнаружено, его потребуется сравнить только с одним именем. Поэтому в наилучшем случае применение
алгоритма сортировки методом вставки к списку из п элементов потребует выполнения
1−n сравнений. (Второй элемент
сравнивается с одним элементом (первым), третий элемент – с одним элементом (вторым) и т.д.).
И наоборот, наихудший сценарий имеет место в том случае, когда каждый опорный элемент потребуется сравнивать со
всеми впереди стоящими элементами, прежде чем удастся найти правильное место его расположения. Очевидно, что в этом
случае исходный список упорядочен в обратном порядке. Первый опорный элемент (второй элемент списка) сравнивается с
одним элементом, второй опорный элемент (третий элемент списка) – с двумя элементами и т.д. (рис. 4.17). Следовательно,
общее количество сравнений при сортировке списка из n элементов составит
()
1...321 −++
+
+
n , что эквивалентно
()
2/1−nn или 1/2(n
2
– n). В частности, для списка из 10 элементов алгоритму сортировки методом вставки в наихудшем слу-
чае потребуется выполнить 45 сравнений.
В среднем при сортировке методом вставки можно ожидать, что каждый опорный элемент потребуется сравнить с по-
ловиной предшествующих ему элементов. В этом случае общее количество выполненных сравнений будет вдвое меньше,
чем в наихудшем случае, т.е. (1/4)(п
2
– п) сравнений для списка длины п. Например, если использовать сортировку методом
вставки для упорядочения множества списков из 10 элементов, то среднее число производимых в каждом случае сравнений
будет равно 22,5.
Важность полученного выше результата состоит в том, что количество сравнений, выполненных алгоритмом сортиров-
ки методом вставки, позволяет оценить время, которое потребуется для выполнения сортировки. Эта оценка была использо-
вана для построения графика, представленного на рис. 4.18. Он показывает, как будет возрастатьвремя, необходимое для
выполнения сортировки методом вставки, при увеличении длины сортируемого списка.
Рис. 4.17. Работа алгоритма сортировки методом вставки
в наихудшем случае
Данный график построен по оценкам работы алгоритма в наихудшем случае, когда, исходя из результатов наших исследова-
ний, для списка длиной п требуется выполнить не менее
(
)
nn −
2
2/1 сравнений элементов. На графике отмечено несколько
конкретных значений длины списка и указано время, необходимое в каждом случае. Обратите внимание, при увеличении
длины списка на одно и то же количество элементов время, необходимое для сортировки списка, все больше и больше возрастает.
Таким образом, с увеличением длины списка эффективность данного алгоритма уменьшается.
Рис. 4.18. График зависимости времени сортировки от длины списка
при сортировке методом вставки
Выполним аналогичный анализ работы алгоритма двоичного поиска в наихудшем случае. Как было установлено выше,
при использовании этого алгоритма для поиска в списке из п элементов потребуется проанализировать не более log
2
n эле-
ментов. Это позволяет оценить время, необходимое для выполнения алгоритма при различной длине сортируемого списка.
На рис. 4.19 представлен график, построенный по результатам данного анализа. На этом графике также отмечены конкрет-
ные значения длины списка, возрастающие на одну и ту же величину, и указано соответствующее время выполнения алго-
ритма. Обратите внимание, что темпы роста времени выполнения алгоритма снижаются по мере увеличения длины списка,
т.е. эффективность алгоритма двоичного поиска возрастает с увеличением длины списка.
Страницы
- « первая
- ‹ предыдущая
- …
- 97
- 98
- 99
- 100
- 101
- …
- следующая ›
- последняя »
