Презентация Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов абсолютно бесплатно. Урок-презентация на эту тему содержит всего 44 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:44 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:490.42 kB
- Просмотров:66
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов.
Лекция 13
№2 слайд
Содержание слайда: АЛГОРИТМЫ И СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
Понятие и свойства алгоритма
Язык блок-схем
Простая программа, cтруктурный подход к разработке алгоритмов
Основные структуры алгоритмов
Язык проектирования программ (псевдокод)
Рекурсивные алгоритмы
Алгоритмы поиска
Алгоритмы сортировки
Принципы объектно-ориентированного программирования
№3 слайд
Содержание слайда:
№4 слайд
Содержание слайда:
№5 слайд
Содержание слайда:
№6 слайд
Содержание слайда:
№7 слайд
Содержание слайда:
№8 слайд
Содержание слайда:
№9 слайд
Содержание слайда:
№10 слайд
Содержание слайда:
№11 слайд
Содержание слайда:
№12 слайд
Содержание слайда:
№13 слайд
Содержание слайда:
№14 слайд
Содержание слайда:
№15 слайд
Содержание слайда:
№16 слайд
Содержание слайда:
№17 слайд
Содержание слайда:
№18 слайд
Содержание слайда:
№19 слайд
Содержание слайда:
№20 слайд
Содержание слайда:
№21 слайд
Содержание слайда:
№22 слайд
Содержание слайда:
№23 слайд
Содержание слайда:
№24 слайд
Содержание слайда:
№25 слайд
Содержание слайда:
№26 слайд
Содержание слайда:
№27 слайд
Содержание слайда:
№28 слайд
Содержание слайда:
№29 слайд
Содержание слайда:
№30 слайд
Содержание слайда:
№31 слайд
Содержание слайда:
№32 слайд
Содержание слайда:
№33 слайд
Содержание слайда:
№34 слайд
Содержание слайда: Длительность работы алгоритма
Несмотря на то, что в некоторых случаях можно определить точное время работы алгоритма, обычно не стоит выполнять оценку с большой точностью.
Для достаточно больших входных данных постоянные множители и слагаемые низшего порядка, фигурирующие в выражении для точного времени работы алгоритма, подавляются эффектами, вызванными увеличением размера ввода.
№35 слайд
Содержание слайда: Длительность работы алгоритма
Рассматривая входные данные достаточно больших размеров для оценки только такой величины, как порядок роста времени работы алгоритма, мы тем самым изучаем асимптотическую эффективность алгоритмов.
Это означает, что нас интересует только то, как время работы алгоритма растет с увеличением размера входных данных в пределе, когда этот размер увеличивается до бесконечности.
Обычно алгоритм, более эффективный в асимптотическом смысле, будет более производительным для всех входных данных, за исключением очень маленьких.
№36 слайд
Содержание слайда: Асимптотические обозначения
Обозначения, используемые для описания асимптотического поведения времени работы алгоритма, используют функции, область определения которых — множество неотрицательных целых чисел N = {0,1,2,...}.
Подобные обозначения удобны для описания времени работы Т (n) в наихудшем случае, как функции, определенной только для целых чисел, представляющих собой размер входных данных.
№37 слайд
Содержание слайда: Асимптотические обозначения
Однако иногда удобно изменить толкование асимптотических обозначений тем или иным образом. Например, эти обозначения легко обобщаются на область действительных чисел или, наоборот, ограничиваются до области, являющейся подмножеством натуральных чисел.
При этом важно понимать точный смысл обозначений, чтобы изменение толкования не привело к неверному их использованию.
№38 слайд
Содержание слайда: θ-обозначения
Время работы алгоритма сортировки методом вставок в наихудшем случае выражается функцией Т (п) = θ (n2). Давайте разберемся в смысле данного обозначения. Для некоторой функции g (п) запись θ (g (п)) обозначает множество функций
№39 слайд
Содержание слайда: “f (n) Є θ (g(п))”
“f (n) Є θ (g(п))”
Это означает, что функция f(п) принадлежит множеству θ (g(п)) (другими словами, является его элементом).
будем использовать эквивалентную запись
“f (n) = θ (g(п))”.
Такое толкование знака равенства для обозначения принадлежности множеству поначалу может сбить с толку, однако далее мы убедимся, что у нее есть свои преимущества.
№40 слайд
Содержание слайда: рассмотрим небольшой пример, в котором с помощью формального определения доказывается, что n2/2 — 3n = θ(n2)
рассмотрим небольшой пример, в котором с помощью формального определения доказывается, что n2/2 — 3n = θ(n2)
№41 слайд
Содержание слайда: О-обозначения
В θ-обозначениях функция асимптотически ограничивается сверху и снизу. Если же достаточно определить только асимптотическую верхнюю границу, используются О-обозначения.
Для данной функции g(n) обозначение O(g(n)) (произносится “о большое от g от n” или просто “о от g от n”) означает множество функций, таких что
№42 слайд
Содержание слайда: О-обозначения
Чтобы записать время работы алгоритма в О-обозначениях, нередко достаточно просто изучить его общую структуру.
Например, наличие двойного вложенного цикла в структуре алгоритма сортировки по методу вставок свидетельствует о том, что верхний предел времени работы в наихудшем
случае выражается как О (n2): “стоимость” каждой итерации во внутреннем цикле ограничена сверху константой O(1), индексы i и j — числом n, а внутренний цикл выполняется самое большее один раз для каждой из n2 пар значений i и j.
№43 слайд
Содержание слайда: О-обозначения
Поскольку О-обозначения описывают верхнюю границу, то в ходе их использования для ограничения времени работы алгоритма в наихудшем случае мы получаем верхнюю границу этой величины для любых входных данных.
Таким образом, граница О (n2) для времени работы алгоритма в наихудшем случае применима для времени решения задачи с любыми входными данными, чего нельзя сказать о θ-обозначениях.
№44 слайд
Содержание слайда: Ω-обозначения
Аналогично тому, как в О-обозначениях дается асимптотическая верхняя граница функции, в Ω-обозначениях дается ее асимптотическая нижняя граница. Для данной функции g (п) выражение Ω (g (n)) (произносится “омега большое от g от n” или просто “омега от g от n”) обозначает множество функций, таких что
Скачать все slide презентации Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов одним архивом:
