ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ СОРТИРОВКИ

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

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

Поэтому традиционной мерой трудоемкости сортировок являются средние количества необходимых сравнений ключей (С) и число пересылок или перестановок элементов (Р), рассматриваемые как функции числа п сортируемых элементов. Хорошие алгоритмы сортировки требуют порядка п • ^2(я) сравнений, а простые — порядка п2 сравнений и эффективны только при малых значениях длины входа.

 
< Пред   СОДЕРЖАНИЕ     След >