Презентация Основы программирования. Анализ трудоемкости алгоритмов онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Основы программирования. Анализ трудоемкости алгоритмов абсолютно бесплатно. Урок-презентация на эту тему содержит всего 14 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:14 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:933.20 kB
- Просмотров:69
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Основы программирования
Анализ трудоемкости алгоритмов
№2 слайд
Содержание слайда: Трудоемкость алгоритма
Элементарный шаг – это действие, время выполнения которого не зависит от числа входных переменных и их значений.
Трудоемкость – это функция зависимости количества элементарных действий от входного параметра n при n→∞ (асимптотическая трудоемкость).
На практике важно не точное значение, а порядок роста T(n) при n →∞.
Используется обозначение , если существуют такие константы ,
что
№3 слайд
Содержание слайда: Типичные случаи для трудоемкости
- логарифмическая, (отличаются в const раз)
- линейная
- линейно-логарифмическая
– полиномиальная
– экспоненциальная,
для случая , т.е. разница в раз.
№4 слайд
Содержание слайда: Соотношения для оценки и сравнения трудоемкостей
выполняется:
Формула Стирлинга для больших значений :
№5 слайд
Содержание слайда: Типы трудоемкостей
Трудоемкость в наихудшем
Трудоемкость в наилучшем
Трудоемкость в среднем:
для генеральной совокупности всех случаев выполнения алгоритма на разных входах с вероятностями и трудоемкостями
вычисляется
Эффективный алгоритм:
имеет наилучшее соотношение трудоемкости и емкостной сложности или
имеет трудоемкость на уровне известной нижней границы
№6 слайд
Содержание слайда: Алгоритмы, основанные на сравнениях
Пусть имеется множество решений .
Первое сравнение приводит к разделению всего множества решений на два подмножества и выбору одного из них. После 2 сравнений мы потенциально можем проверить различных подмножеств, после сравнений - .
Наша цель – выйти на одно из конечных решений. Гарантированно сделать это за сравнений для любого входа можно только при , т.е. при – это минимальная гарантированная трудоемкость в наихудшем для алгоритмов основанных на сравнениях.
№7 слайд
Содержание слайда: Поиск в массиве
Мощность множества решений .
В неупорядоченном массиве .
Для дихотомического поиска:
в общем случае , и при первом разделении массив делится на части длины и , причем .
Поэтому требуется не более разделений массива и, т.е. совпадает с минимальной гарантированной трудоемкостью в наихудшем. Следовательно, алгоритм дихотомического поиска является эффективным.
№8 слайд
Содержание слайда: 1-я теорема о временной сложности
Пусть трудоемкость можно представить соотношением
Тогда:
1. при
2. , при .
Доказательство основано на последовательном разложении рекуррентного соотношения.
№9 слайд
Содержание слайда: 1-я теорема о временной сложности
Доказательство:
1. При и больших :
2. Если , то минимальна при :
В случае порядок сохраняется
№10 слайд
Содержание слайда: Примеры использования 1-й теоремы
Все простые алгоритмы сортировки массива длины n:
Рекурсивный алгоритм для чисел Фибоначчи:
Задача «Ханойские башни»:
№11 слайд
Содержание слайда: 2-я теорема о временной сложности
Пусть трудоемкость можно представить соотношением
Тогда:
1. при
2. при
3. при
Доказательство основано на последовательном разложении рекуррентного соотношения.
№12 слайд
Содержание слайда: 2-я теорема о временной сложности
Доказательство: положим , тогда
где .
№13 слайд
Содержание слайда: 2-я теорема о временной сложности
1. Если , то
2. Если , то
3. Если , то
где и .
Порядок сохраняется и при .
№14 слайд
Содержание слайда: Примеры использования 2-й теоремы
Дихотомический поиск в массиве длины n:
Рекурсивная сортировка слиянием:
Скачать все slide презентации Основы программирования. Анализ трудоемкости алгоритмов одним архивом:
