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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Теорема о сложности сортировки, слайд №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) Вопрос: До какого предела можно снижать трудоемкость сортировки?
Описание слайда:
Изученные ранее методы сортировки имели порядок сложности: О() -> О() -> О(n) Вопрос: До какого предела можно снижать трудоемкость сортировки?

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


Для пересылок: Для пересылок: если мы определили требуемую перестановку и имеем память для второй копии массива, то достаточно сделать n пересылок. На сегодняшний день алгоритм, имеющий n log2 n сравнений и n пересылок, неизвестен. Рассмотрим метод сортировки, самый быстрый из известных.
Описание слайда:
Для пересылок: Для пересылок: если мы определили требуемую перестановку и имеем память для второй копии массива, то достаточно сделать 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. Затем к каждой части будем применять тот же алгоритм.
Описание слайда:
Метод Хоара (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<=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) Алгоритм на псевдокоде 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

Слайд 10


К У Р А П О В А Е К У Р А П О В А Е Е У Р А П О В А К Е А Р А П О В У К Е А В А П О Р У К Е А В А
Описание слайда:
К У Р А П О В А Е К У Р А П О В А Е Е У Р А П О В А К Е А Р А П О В У К Е А В А П О Р У К Е А В А

Слайд 11


А А В Е А А В Е А А В А А В А В
Описание слайда:
А А В Е А А В Е А А В А А В А В

Слайд 12


П О Р У К П О Р У К К О Р У П К О Р У П П У Р У Р Р У
Описание слайда:
П О Р У К П О Р У К К О Р У П К О Р У П П У Р У Р Р У

Слайд 13


Трудоемкость алгоритма QuickSort существенно зависит от того, как соотносится выбираемый элемент Х с остальными элементами в массиве. Трудоемкость алгоритма QuickSort существенно зависит от того, как соотносится выбираемый элемент Х с остальными элементами в массиве. Рассмотрим два крайних случая: 1) Х = min(max) (aL ,…, aR) В этом случае после разделения в одной части массива будет оставаться только один элемент, а в другой части - все остальные. C1 = (n+2)+(n+1)+…+2 = M1 = 3(n-1) Трудоемкость в этом случае сравнима с методом прямого выбора: O(n2), n∞
Описание слайда:
Трудоемкость алгоритма 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 итерации.
Описание слайда:
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) – близкое к минимально возможному значению.
Описание слайда:
Пример. 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∞
Описание слайда:
Итак, количество сравнений 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<0) return 0; if (n==0) return 1; return (n*fact(n-1)); }
Описание слайда:
Проблема глубины рекурсии В теле подпрограммы доступны все объекты, описанные в основной программе, в том числе и имя самой подпрограммы. Это позволяет внутри тела подпрограммы осуществлять вызов самой подпрограммы. Определение. Процедуры и функции, организующие вызовы «самих себя» называются рекурсивными. Многие математические алгоритмы используют рекурсию, поэтому рекурсия широко используется в программировании. Пример: Известный алгоритм вычисления факториала неотрицательного целого числа: 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)); }

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


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

Слайд 20


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

Слайд 21


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

Слайд 22


Алгоритм на псевдокоде Алгоритм на псевдокоде 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 фреймов в памяти.
Описание слайда:
Алгоритм на псевдокоде Алгоритм на псевдокоде 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 фреймов в памяти.

Слайд 23


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

Слайд 24


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию