Презентация - Программирование (лекция 2) Анализ алгоритмов

Нажмите для просмотра
Программирование (лекция 2) Анализ алгоритмов
Распечатать
  • Уникальность: 91%
  • Слайдов: 23
  • Просмотров: 4550
  • Скачиваний: 2427
  • Размер: 6.3 MB
  • Онлайн: Да
  • Формат: ppt / pptx
В закладки
Оцени!
  Помогли? Поделись!

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

Слайд 1

Программирование (лекция 2) Анализ алгоритмов, слайд 1
Программирование Лекция 2. Анализ алгоритмов

Слайд 2

Программирование (лекция 2) Анализ алгоритмов, слайд 2
Алгоритмы являются принципиально важным компонентом информатики, т. к. их изучение не требует использования языка программирования или компьютера. Это означает необходимость в методах, позволяющих сравнивать эффективность алгоритмов, не прибегая к их реализации. Самыми значимыми из этих инструментов являются модель вычислений RAM и асимптотический анализ сложности наихудших случаев.

Слайд 3

Программирование (лекция 2) Анализ алгоритмов, слайд 3
Модель вычислений RAM Разработка машинно-независимых алгоритмов основывается на гипотетическом компьютере, называющемся машиной с произвольным доступом к памяти (Random Access Machine) или RAM-машиной . Согласно этой модели наш компьютер работает таким образом: для исполнения любой простой операции ( , , -, , if) требуется ровно один временной шаг; циклы и подпрограммы не считаются простыми операциями, а состоят из нескольких простых операций. Нет смысла считать подпрограмму сортировки одношаговой операцией, т. к. для сортировки 1 000 000 элементов потребуется определенно намного больше времени, чем для сортировки десяти элементов. Время исполнения цикла или подпрограммы зависит от количества итераций или специфического характера подпрограммы; каждое обращение к памяти занимает один временной шаг. Кроме этого, наш компьютер обладает неограниченным объемом оперативной памяти. Кэш и диск в модели RAM не применяются.

Слайд 4

Программирование (лекция 2) Анализ алгоритмов, слайд 4
Анализ сложности наилучшего, наихудшего и среднего случая С помощью RAM-модели можно подсчитать количество шагов, требуемых алгоритму для исполнения любого экземпляра задачи. Но чтобы получить общее представление о том, насколько хорошим или плохим является алгоритм, нам нужно знать, как он работает со всеми экземплярами задачи. Чтобы понять, что означает наилучший, наихудший и средний случай сложности алгоритма (т. е. время его исполнения в соответствующем случае), нужно рассмотреть исполнение алгоритма на всех возможных экземплярах входных данных. В случае задачи сортировки множество входных экземпляров состоит из всех возможных компоновок ключей n по всем возможным значениям n .

Слайд 5

Программирование (лекция 2) Анализ алгоритмов, слайд 5
Анализ сложности наилучшего, наихудшего и среднего случая На практике наиболее важной является оценка сложности алгоритма в наихудшем случае!

Слайд 6

Программирование (лекция 2) Анализ алгоритмов, слайд 6
Асимптотические обозначения Намного легче работать с верхней и нижней границами функций временной сложности, используя для этого асимптотические обозначения ( -большое и - большое соответственно). - Неудобно пользоваться

Слайд 7

Программирование (лекция 2) Анализ алгоритмов, слайд 7
Асимптотические обозначения

Слайд 8

Программирование (лекция 2) Анализ алгоритмов, слайд 8
Анализ наихудшего случая и асимптотические обозначения являются инструментами, которые существенно упрощают задачу сравнения эффективности алгоритмов.

Слайд 9

Программирование (лекция 2) Анализ алгоритмов, слайд 9

Слайд 10

Программирование (лекция 2) Анализ алгоритмов, слайд 10

Слайд 11

Программирование (лекция 2) Анализ алгоритмов, слайд 11
Скорость роста и отношения доминирования Используя асимптотические обозначения, мы пренебрегаем постоянными множителями, не учитывая их при вычислении функций. При таком подходе функции f(n) 0,001n 2 и g(n) 1000n 2 для нас одинаковы, несмотря на то, что значение функции g(n) в миллион раз больше значения функции f(n) для любого n .

Слайд 12

Программирование (лекция 2) Анализ алгоритмов, слайд 12
Скорость роста основных функций Время исполнения f(n) операций алгоритмов на быстродействующем компьютере, исполняющем каждую операцию за одну наносекунду (10 -9 секунд).

Слайд 13

Программирование (лекция 2) Анализ алгоритмов, слайд 13
Отношения доминирования факториальные показательные кубические квадратичные суперлинейные линейные логарифмические функции-константы

Слайд 14

Программирование (лекция 2) Анализ алгоритмов, слайд 14
Сложение и умножение функций n 3 n 2 n 1 O(n 3 )

Слайд 15

Программирование (лекция 2) Анализ алгоритмов, слайд 15

Слайд 16

Программирование (лекция 2) Анализ алгоритмов, слайд 16
Оценка эффективности Сортировка методом выбора: При сортировке этим способом определяется наименьший неотсортированный элемент и помещается в конец отсортированной части массива. Процедура повторяется до тех пор, пока все элементы массива не будут отсортированы.

Слайд 17

Программирование (лекция 2) Анализ алгоритмов, слайд 17
Оценка эффективности

Слайд 18

Программирование (лекция 2) Анализ алгоритмов, слайд 18
Умножение матриц

Слайд 19

Программирование (лекция 2) Анализ алгоритмов, слайд 19
Оценка эффективности

Слайд 20

Программирование (лекция 2) Анализ алгоритмов, слайд 20
Логарифмы и их применения Логарифм – это функция, обратная показательной. Показательные функции возрастают чрезвычайно быстро. Соответственно, функции, обратные показательным, т.е. логарифмы, возрастают довольно медленно.

Слайд 21

Программирование (лекция 2) Анализ алгоритмов, слайд 21
Логарифмы и двоичный поиск Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия ) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Массив разбивается пополам на каждом вызове до тех пор, пока мы не достигнем единицы. Запишем количество элементов в массиве на каждом вызове: 0-я итерация: n 1-я итерация: n / 2 2-я итерация: n / 4 3-я итерация: n / 8 i-я итерация: n / 2 i последняя итерация: 1 1 n / 2 i 2 i n i log(n)

Слайд 22

Программирование (лекция 2) Анализ алгоритмов, слайд 22
Быстрое возведение в степень Допустим, что нужно вычислить точное значение a n для достаточно большого значения n . Самый простой алгоритм выполняет ( n-1 ) операцию умножения (a a a a). Но можно указать лучший способ решения этой задачи, приняв во внимание, что n n/2 n/2 . Для вычисления конечного значения будет достаточно O(log n) операций умножения.

Слайд 23

Программирование (лекция 2) Анализ алгоритмов, слайд 23
Логарифмы и система уголовного судопроизводства Рекомендуемые наказания в федеральных судах США за преступления финансового мошенничества Мораль логарифмического роста функций ясна: уж если воровать, так миллионы. Логарифмические функции возникают при решении задач с повторяющимся делением или удваиванием входных данных.
^ Наверх
X

Благодарим за оценку!

Мы будем признательны, если Вы так же поделитесь этой презентацией со своими друзьями и подписчиками.

Закрыть (X)