🗊Презентация Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №1Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №2Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №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Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №37Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №38Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №39Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №40Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №41Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №42Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №43Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №44
Скачать

Содержание ▲

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

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

Слайд 1


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов. Лекция 13
Описание слайда:
Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов. Лекция 13

Слайд 2


АЛГОРИТМЫ И СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ Понятие и свойства алгоритма Язык блок-схем Простая программа, cтруктурный подход к разработке алгоритмов Основные структуры алгоритмов Язык проектирования программ (псевдокод) Рекурсивные алгоритмы Алгоритмы поиска Алгоритмы сортировки Принципы объектно-ориентированного программирования
Описание слайда:
АЛГОРИТМЫ И СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ Понятие и свойства алгоритма Язык блок-схем Простая программа, cтруктурный подход к разработке алгоритмов Основные структуры алгоритмов Язык проектирования программ (псевдокод) Рекурсивные алгоритмы Алгоритмы поиска Алгоритмы сортировки Принципы объектно-ориентированного программирования

Слайд 3


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №3
Описание слайда:

Слайд 4


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №4
Описание слайда:

Слайд 5


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №5
Описание слайда:

Слайд 6


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №6
Описание слайда:

Слайд 7


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №7
Описание слайда:

Слайд 8


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №8
Описание слайда:

Слайд 9


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №9
Описание слайда:

Слайд 10


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №10
Описание слайда:

Слайд 11


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №11
Описание слайда:

Слайд 12


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №12
Описание слайда:

Слайд 13


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №13
Описание слайда:

Слайд 14


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №14
Описание слайда:

Слайд 15


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №15
Описание слайда:

Слайд 16


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №16
Описание слайда:

Слайд 17


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №17
Описание слайда:

Слайд 18


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №18
Описание слайда:

Слайд 19


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №19
Описание слайда:

Слайд 20


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №20
Описание слайда:

Слайд 21


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №21
Описание слайда:

Слайд 22


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №22
Описание слайда:

Слайд 23


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №23
Описание слайда:

Слайд 24


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №24
Описание слайда:

Слайд 25


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №25
Описание слайда:

Слайд 26


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №26
Описание слайда:

Слайд 27


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №27
Описание слайда:

Слайд 28


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №28
Описание слайда:

Слайд 29


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №29
Описание слайда:

Слайд 30


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №30
Описание слайда:

Слайд 31


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №31
Описание слайда:

Слайд 32


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №32
Описание слайда:

Слайд 33


Понятие алгоритма. Характеристики алгоритмов и оценка эффективности алгоритмов, слайд №33
Описание слайда:

Слайд 34


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

Слайд 35


Длительность работы алгоритма Рассматривая входные данные достаточно больших размеров для оценки только такой величины, как порядок роста времени работы алгоритма, мы тем самым изучаем асимптотическую эффективность алгоритмов. Это означает, что нас интересует только то, как время работы алгоритма растет с увеличением размера входных данных в пределе, когда этот размер увеличивается до бесконечности. Обычно алгоритм, более эффективный в асимптотическом смысле, будет более производительным для всех входных данных, за исключением очень маленьких.
Описание слайда:
Длительность работы алгоритма Рассматривая входные данные достаточно больших размеров для оценки только такой величины, как порядок роста времени работы алгоритма, мы тем самым изучаем асимптотическую эффективность алгоритмов. Это означает, что нас интересует только то, как время работы алгоритма растет с увеличением размера входных данных в пределе, когда этот размер увеличивается до бесконечности. Обычно алгоритм, более эффективный в асимптотическом смысле, будет более производительным для всех входных данных, за исключением очень маленьких.

Слайд 36


Асимптотические обозначения Обозначения, используемые для описания асимптотического поведения времени работы алгоритма, используют функции, область определения которых — множество неотрицательных целых чисел N = {0,1,2,...}. Подобные обозначения удобны для описания времени работы Т (n) в наихудшем случае, как функции, определенной только для целых чисел, представляющих собой размер входных данных.
Описание слайда:
Асимптотические обозначения Обозначения, используемые для описания асимптотического поведения времени работы алгоритма, используют функции, область определения которых — множество неотрицательных целых чисел N = {0,1,2,...}. Подобные обозначения удобны для описания времени работы Т (n) в наихудшем случае, как функции, определенной только для целых чисел, представляющих собой размер входных данных.

Слайд 37


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

Слайд 38


θ-обозначения Время работы алгоритма сортировки методом вставок в наихудшем случае выражается функцией Т (п) = θ (n2). Давайте разберемся в смысле данного обозначения. Для некоторой функции g (п) запись θ (g (п)) обозначает множество функций
Описание слайда:
θ-обозначения Время работы алгоритма сортировки методом вставок в наихудшем случае выражается функцией Т (п) = θ (n2). Давайте разберемся в смысле данного обозначения. Для некоторой функции g (п) запись θ (g (п)) обозначает множество функций

Слайд 39


“f (n) Є θ (g(п))” “f (n) Є θ (g(п))” Это означает, что функция f(п) принадлежит множеству θ (g(п)) (другими словами, является его элементом). будем использовать эквивалентную запись “f (n) = θ (g(п))”. Такое толкование знака равенства для обозначения принадлежности множеству поначалу может сбить с толку, однако далее мы убедимся, что у нее есть свои преимущества.
Описание слайда:
“f (n) Є θ (g(п))” “f (n) Є θ (g(п))” Это означает, что функция f(п) принадлежит множеству θ (g(п)) (другими словами, является его элементом). будем использовать эквивалентную запись “f (n) = θ (g(п))”. Такое толкование знака равенства для обозначения принадлежности множеству поначалу может сбить с толку, однако далее мы убедимся, что у нее есть свои преимущества.

Слайд 40


рассмотрим небольшой пример, в котором с помощью формального определения доказывается, что n2/2 — 3n = θ(n2) рассмотрим небольшой пример, в котором с помощью формального определения доказывается, что n2/2 — 3n = θ(n2)
Описание слайда:
рассмотрим небольшой пример, в котором с помощью формального определения доказывается, что n2/2 — 3n = θ(n2) рассмотрим небольшой пример, в котором с помощью формального определения доказывается, что n2/2 — 3n = θ(n2)

Слайд 41


О-обозначения В θ-обозначениях функция асимптотически ограничивается сверху и снизу. Если же достаточно определить только асимптотическую верхнюю границу, используются О-обозначения. Для данной функции g(n) обозначение O(g(n)) (произносится “о большое от g от n” или просто “о от g от n”) означает множество функций, таких что
Описание слайда:
О-обозначения В θ-обозначениях функция асимптотически ограничивается сверху и снизу. Если же достаточно определить только асимптотическую верхнюю границу, используются О-обозначения. Для данной функции g(n) обозначение O(g(n)) (произносится “о большое от g от n” или просто “о от g от n”) означает множество функций, таких что

Слайд 42


О-обозначения Чтобы записать время работы алгоритма в О-обозначениях, нередко достаточно просто изучить его общую структуру. Например, наличие двойного вложенного цикла в структуре алгоритма сортировки по методу вставок свидетельствует о том, что верхний предел времени работы в наихудшем случае выражается как О (n2): “стоимость” каждой итерации во внутреннем цикле ограничена сверху константой O(1), индексы i и j — числом n, а внутренний цикл выполняется самое большее один раз для каждой из n2 пар значений i и j.
Описание слайда:
О-обозначения Чтобы записать время работы алгоритма в О-обозначениях, нередко достаточно просто изучить его общую структуру. Например, наличие двойного вложенного цикла в структуре алгоритма сортировки по методу вставок свидетельствует о том, что верхний предел времени работы в наихудшем случае выражается как О (n2): “стоимость” каждой итерации во внутреннем цикле ограничена сверху константой O(1), индексы i и j — числом n, а внутренний цикл выполняется самое большее один раз для каждой из n2 пар значений i и j.

Слайд 43


О-обозначения Поскольку О-обозначения описывают верхнюю границу, то в ходе их использования для ограничения времени работы алгоритма в наихудшем случае мы получаем верхнюю границу этой величины для любых входных данных. Таким образом, граница О (n2) для времени работы алгоритма в наихудшем случае применима для времени решения задачи с любыми входными данными, чего нельзя сказать о θ-обозначениях.
Описание слайда:
О-обозначения Поскольку О-обозначения описывают верхнюю границу, то в ходе их использования для ограничения времени работы алгоритма в наихудшем случае мы получаем верхнюю границу этой величины для любых входных данных. Таким образом, граница О (n2) для времени работы алгоритма в наихудшем случае применима для времени решения задачи с любыми входными данными, чего нельзя сказать о θ-обозначениях.

Слайд 44


Ω-обозначения Аналогично тому, как в О-обозначениях дается асимптотическая верхняя граница функции, в Ω-обозначениях дается ее асимптотическая нижняя граница. Для данной функции g (п) выражение Ω (g (n)) (произносится “омега большое от g от n” или просто “омега от g от n”) обозначает множество функций, таких что
Описание слайда:
Ω-обозначения Аналогично тому, как в О-обозначениях дается асимптотическая верхняя граница функции, в Ω-обозначениях дается ее асимптотическая нижняя граница. Для данной функции g (п) выражение Ω (g (n)) (произносится “омега большое от g от n” или просто “омега от g от n”) обозначает множество функций, таких что

Скачать

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