Презентация Теорема о сложности сортировки онлайн

Содержание слайда: Изученные ранее методы сортировки имели порядок сложности: О() -> О() -> О(n) Вопрос: До какого предела можно снижать трудоемкость сортировки?

Содержание слайда: Теорема. Теорема. Если все перестановки из n элементов равновероятны, то любое дерево решений, сортирующее последовательность из n элементов, имеет среднюю высоту не менее Приведем нестрогое доказательство. Рассмотрим дерево решений для сортировки трех элементов a, b, c.

Содержание слайда:

Содержание слайда: Листья дерева - это все возможные перестановки элементов a, b, c. Листья дерева - это все возможные перестановки элементов a, b, c. Для того, чтобы узнать, какая перестановка нужна для упорядочения элементов a, b, c, достаточно сделать в некоторых случаях 2 сравнения, в других - 3 сравнения: Сср = =

Содержание слайда: Сср = = Сср = = Из теории графов известно, что длина внешнего пути двоичного дерева с m листьями D(m) ≥ m В нашем дереве листьев, поэтому Cср ≥ Cср ≥

Содержание слайда: Используем нижнюю оценку для : Используем нижнюю оценку для : > n – n Cср ≥ n – n Получаем следствие из теоремы: Не существует алгоритма сортировки n элементов, использующего в среднем менее n log2 n – n log2 e операций сравнения. Класс сложности порядка n log2 n является предельно достижимым для алгоритмов, основанных на операциях сравнения.

Содержание слайда: Для пересылок: Для пересылок: если мы определили требуемую перестановку и имеем память для второй копии массива, то достаточно сделать n пересылок. На сегодняшний день алгоритм, имеющий n log2 n сравнений и n пересылок, неизвестен. Рассмотрим метод сортировки, самый быстрый из известных.

Содержание слайда: Метод Хоара (Hoare, 1962) QuickSort Возьмем произвольный элемент массива, обозначим его через Х. Просматривая массив слева, найдем элемент ai ≥ x. Просматривая массив справа, найдем элемент aj ≤ x. ai ≥ x i j aj ≤ x ≤x ≥x Поменяем местами ai и aj. Будем продолжать процесс просмотра и обмена, пока i не станет больше j. В результате массив окажется разделенным на две части: левую с элементами ≤x, и правую с элементами ≥x. Затем к каждой части будем применять тот же алгоритм.

Содержание слайда: Метод Хоара (QuickSort) Алгоритм на псевдокоде L, R – левая и правая границы рабочей части массива   QuickSort ( L, R ) х := аL, i := L, j := R DО ( ij ) DО ( ai < x) i := i+1 OD DО ( aj > x) j := j-1 OD IF ( i<=j ) ai↔aj,, i := i+1, j := j -1 FI OD IF ( L<j ) QuickSort ( L, j ) FI IF ( i<R ) QuickSort ( i, R) FI

Содержание слайда: К У Р А П О В А Е К У Р А П О В А Е Е У Р А П О В А К Е А Р А П О В У К Е А В А П О Р У К Е А В А

Содержание слайда: А А В Е А А В Е А А В А А В А В

Содержание слайда: П О Р У К П О Р У К К О Р У П К О Р У П П У Р У Р Р У

Содержание слайда: Трудоемкость алгоритма QuickSort существенно зависит от того, как соотносится выбираемый элемент Х с остальными элементами в массиве. Трудоемкость алгоритма QuickSort существенно зависит от того, как соотносится выбираемый элемент Х с остальными элементами в массиве. Рассмотрим два крайних случая: 1) Х = min(max) (aL ,…, aR) В этом случае после разделения в одной части массива будет оставаться только один элемент, а в другой части - все остальные. C1 = (n+2)+(n+1)+…+2 = M1 = 3(n-1) Трудоемкость в этом случае сравнима с методом прямого выбора: O(n2), n∞

Содержание слайда: 2) Х = med (aL ,…, aR) – медиана 2) Х = med (aL ,…, aR) – медиана Определение. Элемент am называется медианой для элементов aL ,…, aR , если количество элементов меньших am равно количеству элементов больших am (с точностью до одного элемента). В примере буква К – медиана для КУРАПОВАЕ. В этом случае массив разделяется на две равные части. Определим наименьшее возможное количество сравнений. Возьмем для примера n = 15 (степень двойки), затем массив делится на 7 и 7, затем на 3,3,3,3. Всего потребуется 3 итерации.

Содержание слайда: Пример. X Х Х Х Х Х Х n =-1 n = -1 => k = Из таблицы k = 4, 3 = к-1 - количество итераций. C = (k-1) = ( log(n+1) - 1) = (n+1) log(n+1) - (n+1) – близкое к минимально возможному значению.

Содержание слайда: Итак, количество сравнений C = n log n Итак, количество сравнений C = n log n Количество пересылок зависит от расположения элементов, но не может быть больше одного обмена (3 пересылки) на два сравнения. Поэтому количество пересылок – величина того же порядка, что и количество сравнений: М = n log n. Средняя трудоемкость QiuckSort: O (n log n), n∞

Содержание слайда: Проблема глубины рекурсии В теле подпрограммы доступны все объекты, описанные в основной программе, в том числе и имя самой подпрограммы. Это позволяет внутри тела подпрограммы осуществлять вызов самой подпрограммы. Определение. Процедуры и функции, организующие вызовы «самих себя» называются рекурсивными. Многие математические алгоритмы используют рекурсию, поэтому рекурсия широко используется в программировании. Пример: Известный алгоритм вычисления факториала неотрицательного целого числа: 0! = 1, 1! = 1, n! = (n-1)! n. long fact (int n) { if (n<0) return 0; if (n==0) return 1; return (n*fact(n-1)); }

Содержание слайда: Вычисление 4! fact (4) (((1*1)*2)*3)*4 fact(3) ((1*1)*2)*3 fact(2) (1*1)*2 fact(1) 1*1 fact(0) 1 Рекурсивное выполнение программы более компактно и наглядно, но существует опасность переполнения стека.

Содержание слайда:

Содержание слайда:

Содержание слайда: Вместо двух рекурсивных вызовов Вместо двух рекурсивных вызовов (для левой и правой части массива) будем использовать только один рекурсивный вызов, а другой заменим новой итерацией цикла. Вопрос: Для какой части массива нужно делать рекурсивный вызов, чтобы уменьшить глубину рекурсии? Ответ: Для меньшей по размеру части массива. !-------------!--------------------------------! L J I R

Содержание слайда: Алгоритм на псевдокоде Алгоритм на псевдокоде QuickSort(L,R) (вторая версия) DO ( L<R ) <Разделение на две части> IF ( j-L < R-i ) QuickSort( L, j ), L := i ELSE QuickSort( i, R ), R := j FI OD В этом случае худший вариант, когда обе части массива равны, тогда глубина рекурсии Пример: для массива из 1 млн. элементов ( n = 1000000 ) понадобится одновременно менее 20 фреймов в памяти.

Содержание слайда: Примеры рекурсии Преподаватель всегда прав. Если преподаватель не прав, смотри пункт 1. Бюрократия разрастается, чтобы удовлетворить нужды разрастающейся бюрократии. Смысл жизни – в достижении её цели, цель жизни – в наполнении ее смыслом. Если у вас украли кредитную карту, позвоните по телефону указанному на оборотной стороне кредитной карты. Для выхода в Интернет, скачайте нашу программу из Интернета. Keyboard not found. Press F1 to continue. Салат : помидоры, огурцы, салат.

Содержание слайда: