Основы программирования. Анализ трудоемкости алгоритмов

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

Основы программирования. Анализ трудоемкости алгоритмов, слайд №2

Основы программирования. Анализ трудоемкости алгоритмов, слайд №3

Основы программирования. Анализ трудоемкости алгоритмов, слайд №4

Основы программирования. Анализ трудоемкости алгоритмов, слайд №5

Основы программирования. Анализ трудоемкости алгоритмов, слайд №6

Основы программирования. Анализ трудоемкости алгоритмов, слайд №7

Основы программирования. Анализ трудоемкости алгоритмов, слайд №8

Основы программирования. Анализ трудоемкости алгоритмов, слайд №9

Основы программирования. Анализ трудоемкости алгоритмов, слайд №10

Основы программирования. Анализ трудоемкости алгоритмов, слайд №11

Основы программирования. Анализ трудоемкости алгоритмов, слайд №12

Основы программирования. Анализ трудоемкости алгоритмов, слайд №13

Основы программирования. Анализ трудоемкости алгоритмов, слайд №14

Содержание ▲

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

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

Слайд 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. при Доказательство основано на последовательном разложении рекуррентного соотношения.