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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Основы программирования. Анализ трудоемкости алгоритмов, слайд №1Основы программирования. Анализ трудоемкости алгоритмов, слайд №2Основы программирования. Анализ трудоемкости алгоритмов, слайд №3Основы программирования. Анализ трудоемкости алгоритмов, слайд №4Основы программирования. Анализ трудоемкости алгоритмов, слайд №5Основы программирования. Анализ трудоемкости алгоритмов, слайд №6Основы программирования. Анализ трудоемкости алгоритмов, слайд №7Основы программирования. Анализ трудоемкости алгоритмов, слайд №8Основы программирования. Анализ трудоемкости алгоритмов, слайд №9Основы программирования. Анализ трудоемкости алгоритмов, слайд №10Основы программирования. Анализ трудоемкости алгоритмов, слайд №11Основы программирования. Анализ трудоемкости алгоритмов, слайд №12Основы программирования. Анализ трудоемкости алгоритмов, слайд №13Основы программирования. Анализ трудоемкости алгоритмов, слайд №14
Скачать
Вы можете ознакомиться и скачать презентацию на тему Основы программирования. Анализ трудоемкости алгоритмов. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


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

Слайд 2


Трудоемкость алгоритма Элементарный шаг – это действие, время выполнения которого не зависит от числа входных переменных и их значений. Трудоемкость – это функция зависимости количества элементарных действий от входного параметра n при n→∞ (асимптотическая трудоемкость). На практике важно не точное значение, а порядок роста T(n) при n →∞. Используется обозначение , если существуют такие константы , что
Описание слайда:
Трудоемкость алгоритма Элементарный шаг – это действие, время выполнения которого не зависит от числа входных переменных и их значений. Трудоемкость – это функция зависимости количества элементарных действий от входного параметра n при n→∞ (асимптотическая трудоемкость). На практике важно не точное значение, а порядок роста T(n) при n →∞. Используется обозначение , если существуют такие константы , что

Слайд 3


Типичные случаи для трудоемкости - логарифмическая, (отличаются в const раз) - линейная - линейно-логарифмическая – полиномиальная – экспоненциальная, для случая , т.е. разница в раз.
Описание слайда:
Типичные случаи для трудоемкости - логарифмическая, (отличаются в const раз) - линейная - линейно-логарифмическая – полиномиальная – экспоненциальная, для случая , т.е. разница в раз.

Слайд 4


Соотношения для оценки и сравнения трудоемкостей выполняется: Формула Стирлинга для больших значений :
Описание слайда:
Соотношения для оценки и сравнения трудоемкостей выполняется: Формула Стирлинга для больших значений :

Слайд 5


Типы трудоемкостей Трудоемкость в наихудшем Трудоемкость в наилучшем Трудоемкость в среднем: для генеральной совокупности всех случаев выполнения алгоритма на разных входах с вероятностями и трудоемкостями вычисляется Эффективный алгоритм: имеет наилучшее соотношение трудоемкости и емкостной сложности или имеет трудоемкость на уровне известной нижней границы
Описание слайда:
Типы трудоемкостей Трудоемкость в наихудшем Трудоемкость в наилучшем Трудоемкость в среднем: для генеральной совокупности всех случаев выполнения алгоритма на разных входах с вероятностями и трудоемкостями вычисляется Эффективный алгоритм: имеет наилучшее соотношение трудоемкости и емкостной сложности или имеет трудоемкость на уровне известной нижней границы

Слайд 6


Алгоритмы, основанные на сравнениях Пусть имеется множество решений . Первое сравнение приводит к разделению всего множества решений на два подмножества и выбору одного из них. После 2 сравнений мы потенциально можем проверить различных подмножеств, после сравнений - . Наша цель – выйти на одно из конечных решений. Гарантированно сделать это за сравнений для любого входа можно только при , т.е. при – это минимальная гарантированная трудоемкость в наихудшем для алгоритмов основанных на сравнениях.
Описание слайда:
Алгоритмы, основанные на сравнениях Пусть имеется множество решений . Первое сравнение приводит к разделению всего множества решений на два подмножества и выбору одного из них. После 2 сравнений мы потенциально можем проверить различных подмножеств, после сравнений - . Наша цель – выйти на одно из конечных решений. Гарантированно сделать это за сравнений для любого входа можно только при , т.е. при – это минимальная гарантированная трудоемкость в наихудшем для алгоритмов основанных на сравнениях.

Слайд 7


Поиск в массиве Мощность множества решений . В неупорядоченном массиве . Для дихотомического поиска: в общем случае , и при первом разделении массив делится на части длины и , причем . Поэтому требуется не более разделений массива и, т.е. совпадает с минимальной гарантированной трудоемкостью в наихудшем. Следовательно, алгоритм дихотомического поиска является эффективным.
Описание слайда:
Поиск в массиве Мощность множества решений . В неупорядоченном массиве . Для дихотомического поиска: в общем случае , и при первом разделении массив делится на части длины и , причем . Поэтому требуется не более разделений массива и, т.е. совпадает с минимальной гарантированной трудоемкостью в наихудшем. Следовательно, алгоритм дихотомического поиска является эффективным.

Слайд 8


1-я теорема о временной сложности Пусть трудоемкость можно представить соотношением Тогда: 1. при 2. , при . Доказательство основано на последовательном разложении рекуррентного соотношения.
Описание слайда:
1-я теорема о временной сложности Пусть трудоемкость можно представить соотношением Тогда: 1. при 2. , при . Доказательство основано на последовательном разложении рекуррентного соотношения.

Слайд 9


1-я теорема о временной сложности Доказательство: 1. При и больших : 2. Если , то минимальна при : В случае порядок сохраняется
Описание слайда:
1-я теорема о временной сложности Доказательство: 1. При и больших : 2. Если , то минимальна при : В случае порядок сохраняется

Слайд 10


Примеры использования 1-й теоремы Все простые алгоритмы сортировки массива длины n: Рекурсивный алгоритм для чисел Фибоначчи: Задача «Ханойские башни»:
Описание слайда:
Примеры использования 1-й теоремы Все простые алгоритмы сортировки массива длины n: Рекурсивный алгоритм для чисел Фибоначчи: Задача «Ханойские башни»:

Слайд 11


2-я теорема о временной сложности Пусть трудоемкость можно представить соотношением Тогда: 1. при 2. при 3. при Доказательство основано на последовательном разложении рекуррентного соотношения.
Описание слайда:
2-я теорема о временной сложности Пусть трудоемкость можно представить соотношением Тогда: 1. при 2. при 3. при Доказательство основано на последовательном разложении рекуррентного соотношения.

Слайд 12


2-я теорема о временной сложности Доказательство: положим , тогда где .
Описание слайда:
2-я теорема о временной сложности Доказательство: положим , тогда где .

Слайд 13


2-я теорема о временной сложности 1. Если , то 2. Если , то 3. Если , то где и . Порядок сохраняется и при .
Описание слайда:
2-я теорема о временной сложности 1. Если , то 2. Если , то 3. Если , то где и . Порядок сохраняется и при .

Слайд 14


Примеры использования 2-й теоремы Дихотомический поиск в массиве длины n: Рекурсивная сортировка слиянием:
Описание слайда:
Примеры использования 2-й теоремы Дихотомический поиск в массиве длины n: Рекурсивная сортировка слиянием:

Скачать

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