Lec_06

Пример работы

21

Рассмотрим работу процедуры для массива a[0]...a[6] и опорного элемента p = a[3].

Свойства алгоритма

22

Каждое разделение требует, очевидно, O(n) операций.

Количество шагов деления (глубина рекурсии) составляет приблизительно log(n), если массив делится на относительно равные части.

Отсюда можно посчитать, что общее быстродействие: O(n*log(n)).

Но если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности, то алгоритм будет работать за O(n2) операций.

Метод неустойчив. Поведение довольно естественно.

Задачи…

23

4.2) Есть массив, содержащий набор чисел в произвольном порядке. Необходимо написать программу, которая проверяет все ли его значения различны. И если это не так, то удалить все повторные вхождения чисел.