Обоснованность такого
Обоснованность такого предположения можно доказать, и мы предлагаем читателю заглянуть в одну из упомянутых в этой главе монографий.
К сожалению, приведенная оценка действует в среднем, но встречаются и исключения, вроде того, которое мы специально привели выше - на рис. E6-1. Есть и другие отрицательные моменты. В частности, если входной набор уже упорядочен, то быстрая сортировка, ничего не переставляя в нем, отработает до конца, то есть будет упорно дробить его вплоть до разделения на N подмассивов единичной длины. Напротив, пузырьковая сортировка с флажком - BubbleSort2 из упражнения в Уроке E5, - чья асимптотическая эффективность заметно хуже, в этом случае уже давно бы остановилась. Столь же неразумным выглядит применение QuickSort к массиву из одинаковых элементов. Насколько медленной может оказаться быстрая сортировка? Ответ прост: если на каждой итерации разделения будет отщипываться подмассив единичной длины. В этом случае трудоемкость составит O(N2).
Упражнение #4.
Смоделируйте
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
