Теорема о сложности сортировки - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Теорема о сложности сортировки, слайд №1

Теорема о сложности сортировки, слайд №2

Теорема о сложности сортировки, слайд №3

Теорема о сложности сортировки, слайд №4

Теорема о сложности сортировки, слайд №5

Теорема о сложности сортировки, слайд №6

Теорема о сложности сортировки, слайд №7

Теорема о сложности сортировки, слайд №8

Теорема о сложности сортировки, слайд №9

Теорема о сложности сортировки, слайд №10

Теорема о сложности сортировки, слайд №11

Теорема о сложности сортировки, слайд №12

Теорема о сложности сортировки, слайд №13

Теорема о сложности сортировки, слайд №14

Теорема о сложности сортировки, слайд №15

Теорема о сложности сортировки, слайд №16

Теорема о сложности сортировки, слайд №17

Теорема о сложности сортировки, слайд №18

Теорема о сложности сортировки, слайд №19

Теорема о сложности сортировки, слайд №20

Теорема о сложности сортировки, слайд №21

Теорема о сложности сортировки, слайд №22

Теорема о сложности сортировки, слайд №23

Теорема о сложности сортировки, слайд №24

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теорема о сложности сортировки. Доклад-сообщение содержит 24 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Метод Хоара (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

Слайд 10

Описание слайда:

К У Р А П О В А Е К У Р А П О В А Е Е У Р А П О В А К Е А Р А П О В У К Е А В А П О Р У К Е А В А

Слайд 11

Описание слайда:

А А В Е А А В Е А А В А А В А В

Слайд 12

Описание слайда:

П О Р У К П О Р У К К О Р У П К О Р У П П У Р У Р Р У

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

Вычисление 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 Рекурсивное выполнение программы более компактно и наглядно, но существует опасность переполнения стека.

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

Алгоритм на псевдокоде Алгоритм на псевдокоде QuickSort(L,R) (вторая версия) DO ( L

Слайд 23

Описание слайда:

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