Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

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

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

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

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

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы