🗊Презентация Анализ алгоритмов. (Лекция 16)

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Анализ алгоритмов. (Лекция 16), слайд №1Анализ алгоритмов. (Лекция 16), слайд №2Анализ алгоритмов. (Лекция 16), слайд №3Анализ алгоритмов. (Лекция 16), слайд №4Анализ алгоритмов. (Лекция 16), слайд №5Анализ алгоритмов. (Лекция 16), слайд №6Анализ алгоритмов. (Лекция 16), слайд №7Анализ алгоритмов. (Лекция 16), слайд №8Анализ алгоритмов. (Лекция 16), слайд №9Анализ алгоритмов. (Лекция 16), слайд №10Анализ алгоритмов. (Лекция 16), слайд №11Анализ алгоритмов. (Лекция 16), слайд №12Анализ алгоритмов. (Лекция 16), слайд №13Анализ алгоритмов. (Лекция 16), слайд №14Анализ алгоритмов. (Лекция 16), слайд №15Анализ алгоритмов. (Лекция 16), слайд №16Анализ алгоритмов. (Лекция 16), слайд №17Анализ алгоритмов. (Лекция 16), слайд №18Анализ алгоритмов. (Лекция 16), слайд №19Анализ алгоритмов. (Лекция 16), слайд №20Анализ алгоритмов. (Лекция 16), слайд №21Анализ алгоритмов. (Лекция 16), слайд №22Анализ алгоритмов. (Лекция 16), слайд №23Анализ алгоритмов. (Лекция 16), слайд №24Анализ алгоритмов. (Лекция 16), слайд №25Анализ алгоритмов. (Лекция 16), слайд №26Анализ алгоритмов. (Лекция 16), слайд №27Анализ алгоритмов. (Лекция 16), слайд №28Анализ алгоритмов. (Лекция 16), слайд №29Анализ алгоритмов. (Лекция 16), слайд №30Анализ алгоритмов. (Лекция 16), слайд №31Анализ алгоритмов. (Лекция 16), слайд №32Анализ алгоритмов. (Лекция 16), слайд №33Анализ алгоритмов. (Лекция 16), слайд №34Анализ алгоритмов. (Лекция 16), слайд №35Анализ алгоритмов. (Лекция 16), слайд №36Анализ алгоритмов. (Лекция 16), слайд №37Анализ алгоритмов. (Лекция 16), слайд №38Анализ алгоритмов. (Лекция 16), слайд №39Анализ алгоритмов. (Лекция 16), слайд №40Анализ алгоритмов. (Лекция 16), слайд №41Анализ алгоритмов. (Лекция 16), слайд №42
Скачать

Содержание ▲

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

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

Слайд 1


Анализ алгоритмов Алтайский государственный университет Факультет математики и ИТ Кафедра информатики Барнаул 2014
Описание слайда:
Анализ алгоритмов Алтайский государственный университет Факультет математики и ИТ Кафедра информатики Барнаул 2014

Слайд 2


Лекция 16 План Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший, средний и лучший случаи Что ускорять: компьютер или алгоритм? Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и пространственная сложность Бинарный поиск Идея алгоритма Временная сложность алгоритма
Описание слайда:
Лекция 16 План Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший, средний и лучший случаи Что ускорять: компьютер или алгоритм? Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и пространственная сложность Бинарный поиск Идея алгоритма Временная сложность алгоритма

Слайд 3


Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший, средний и лучший случаи Что ускорять: компьютер или алгоритм?
Описание слайда:
Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший, средний и лучший случаи Что ускорять: компьютер или алгоритм?

Слайд 4


Эффективность алгоритмов Часто для решения одной и той же задачи могут быть использованы различные алгоритмы Как выбрать алгоритм? При разработке программ преследуется две (часто конфликтующие) цели Разработать алгоритм, простой для понимания, кодирования и отладки Предмет изучения дисциплины «Software Engineering» Разработать алгоритм, эффективно использующий ресурсы компьютера Предмет изучения дисциплины «Структуры данных и анализ алгоритмов»
Описание слайда:
Эффективность алгоритмов Часто для решения одной и той же задачи могут быть использованы различные алгоритмы Как выбрать алгоритм? При разработке программ преследуется две (часто конфликтующие) цели Разработать алгоритм, простой для понимания, кодирования и отладки Предмет изучения дисциплины «Software Engineering» Разработать алгоритм, эффективно использующий ресурсы компьютера Предмет изучения дисциплины «Структуры данных и анализ алгоритмов»

Слайд 5


Эффективность алгоритмов Основные ресурсы Время выполнения алгоритма Определяется количеством тривиальных шагов, необходимых для решения задачи Пространство, используемое алгоритмом Определяется объёмом оперативной памяти или памяти на носителе данных Остается «за скобками» : Трудоемкость кодирования алгоритма Определяется временными затратами программиста на кодирование и отладку алгоритма
Описание слайда:
Эффективность алгоритмов Основные ресурсы Время выполнения алгоритма Определяется количеством тривиальных шагов, необходимых для решения задачи Пространство, используемое алгоритмом Определяется объёмом оперативной памяти или памяти на носителе данных Остается «за скобками» : Трудоемкость кодирования алгоритма Определяется временными затратами программиста на кодирование и отладку алгоритма

Слайд 6


Как измерять эффективность алгоритмов? Возможные пути Экспериментальное (эмпирическое) сравнение алгоритмов Сравнение затрат времени (памяти) при непосредственном запуске программ Асимптотический анализ алгоритмов Построение теоретических оценок затрат времени (памяти) в зависимости от различных факторов
Описание слайда:
Как измерять эффективность алгоритмов? Возможные пути Экспериментальное (эмпирическое) сравнение алгоритмов Сравнение затрат времени (памяти) при непосредственном запуске программ Асимптотический анализ алгоритмов Построение теоретических оценок затрат времени (памяти) в зависимости от различных факторов

Слайд 7


От чего зависит время выполнения? От загрузки машины От операционной системы От компилятора От специфики значений входных данных От размера задачи Зависимость времени выполнения T от размера задачи n выражается некоторой функцией T(n)
Описание слайда:
От чего зависит время выполнения? От загрузки машины От операционной системы От компилятора От специфики значений входных данных От размера задачи Зависимость времени выполнения T от размера задачи n выражается некоторой функцией T(n)

Слайд 8


Зависимость времени от размера Пример 1. Поиск максимума
Описание слайда:
Зависимость времени от размера Пример 1. Поиск максимума

Слайд 9


Характер роста функций В зависимости от вида функции T(n) характер ее роста может быть разным
Описание слайда:
Характер роста функций В зависимости от вида функции T(n) характер ее роста может быть разным

Слайд 10


Наилучший, наихудший и средний случаи При том же размере входных данных n время выполнения алгоритма может быть разным Пример. Последовательный поиск элемента K в массиве размера n Элементы массива, начиная с первого, поочередно просматриваются до тех пор пока не найден K Наилучший случай: K найден на 1-й позиции Наихудший случай: K найден на n-й позиции Средний случай: в среднем K обнаружится после (n+1)/2 сравнений
Описание слайда:
Наилучший, наихудший и средний случаи При том же размере входных данных n время выполнения алгоритма может быть разным Пример. Последовательный поиск элемента K в массиве размера n Элементы массива, начиная с первого, поочередно просматриваются до тех пор пока не найден K Наилучший случай: K найден на 1-й позиции Наихудший случай: K найден на n-й позиции Средний случай: в среднем K обнаружится после (n+1)/2 сравнений

Слайд 11


Какой из случаев оценивать? Анализировать поведение алгоритма в среднем – наиболее разумно, но наиболее трудно Требуется знание распределения значений (частоты возникновения тех или иных данных) Поведение алгоритма в худшем случае важно анализировать в алгоритмах реального времени Пример – системы диспетчеризации транспорта
Описание слайда:
Какой из случаев оценивать? Анализировать поведение алгоритма в среднем – наиболее разумно, но наиболее трудно Требуется знание распределения значений (частоты возникновения тех или иных данных) Поведение алгоритма в худшем случае важно анализировать в алгоритмах реального времени Пример – системы диспетчеризации транспорта

Слайд 12


Ускорять компьютер или алгоритм? Что произойдет, если использовать компьютер в 10 раз производительнее?
Описание слайда:
Ускорять компьютер или алгоритм? Что произойдет, если использовать компьютер в 10 раз производительнее?

Слайд 13


Ускорять компьютер или алгоритм? Абсолютные временные затраты алгоритмов разной сложности
Описание слайда:
Ускорять компьютер или алгоритм? Абсолютные временные затраты алгоритмов разной сложности

Слайд 14


Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и пространственная сложность
Описание слайда:
Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и пространственная сложность

Слайд 15


Асимптотический анализ Экспериментальное сравнение алгоритмов трудоемко На практике чаще используется более простой асимптотический анализ алгоритмов Асимптотический анализ алгоритмов направлен на получение и сравнение теоретических оценок сложности алгоритмов (вида T(n)) при достаточно больших n
Описание слайда:
Асимптотический анализ Экспериментальное сравнение алгоритмов трудоемко На практике чаще используется более простой асимптотический анализ алгоритмов Асимптотический анализ алгоритмов направлен на получение и сравнение теоретических оценок сложности алгоритмов (вида T(n)) при достаточно больших n

Слайд 16


Асимптотический анализ В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе O-символика o(f(n)) оценка порядка малости O(f(n)) оценка верхней границы (f(n)) оценка нижней границы (f(n)) оценка верхней и нижней границы
Описание слайда:
Асимптотический анализ В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе O-символика o(f(n)) оценка порядка малости O(f(n)) оценка верхней границы (f(n)) оценка нижней границы (f(n)) оценка верхней и нижней границы

Слайд 17


Асимптотический анализ: O() Определение Говорят, что неотрицательная функция f(n) есть O(g(n)), если существуют константы c>0 и n0>0, такие что f(n) ≤ cg(n) для любых n > n0. Пример использования Временная сложность алгоритма есть O(n2) в [лучшем, среднем, худшем] случае. Смысл Для всех достаточно больших входных данных (n>n0), алгоритм всегда выполняется менее, чем за cg(n) шагов в [лучшем, среднем, худшем] случае
Описание слайда:
Асимптотический анализ: O() Определение Говорят, что неотрицательная функция f(n) есть O(g(n)), если существуют константы c>0 и n0>0, такие что f(n) ≤ cg(n) для любых n > n0. Пример использования Временная сложность алгоритма есть O(n2) в [лучшем, среднем, худшем] случае. Смысл Для всех достаточно больших входных данных (n>n0), алгоритм всегда выполняется менее, чем за cg(n) шагов в [лучшем, среднем, худшем] случае

Слайд 18


Асимптотический анализ: O() Другими словами Запись f(n)=O(g(n)) означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя. Пример. Если T(n) = 3n2, то T(n) есть O(n2)
Описание слайда:
Асимптотический анализ: O() Другими словами Запись f(n)=O(g(n)) означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя. Пример. Если T(n) = 3n2, то T(n) есть O(n2)

Слайд 19


Асимптотический анализ: O() O() указывает верхнюю границу При выборе верхней границы наиболее интересна наименьшая из возможных Пример. Хотя T(n) = 3n2 есть O(n3), мы выбираем O(n2) как более информативный вариант
Описание слайда:
Асимптотический анализ: O() O() указывает верхнюю границу При выборе верхней границы наиболее интересна наименьшая из возможных Пример. Хотя T(n) = 3n2 есть O(n3), мы выбираем O(n2) как более информативный вариант

Слайд 20


Асимптотический анализ: O() Пример 1. Линейный поиск в массиве (средний случай) T(n) = csn/2 Для всех n > 1, csn/2 ≤ csn Таким образом, по определению, T(n) есть O(n) при n0 = 1 и c = cs
Описание слайда:
Асимптотический анализ: O() Пример 1. Линейный поиск в массиве (средний случай) T(n) = csn/2 Для всех n > 1, csn/2 ≤ csn Таким образом, по определению, T(n) есть O(n) при n0 = 1 и c = cs

Слайд 21


Асимптотический анализ: O() Пример 2. Пусть T(n) = c1n2 + c2n в среднем случае c1n2 + c2n ≤ c1n2 + c2n2 ≤ (c1 + c2)n2 для всех n > 1 T(n) ≤ cn2 при c = c1 + c2 и n0 = 1. Тогда T(n) есть O(n2) по определению Пример 3. T(n) = c. Говорят: T(n) есть O(1).
Описание слайда:
Асимптотический анализ: O() Пример 2. Пусть T(n) = c1n2 + c2n в среднем случае c1n2 + c2n ≤ c1n2 + c2n2 ≤ (c1 + c2)n2 для всех n > 1 T(n) ≤ cn2 при c = c1 + c2 и n0 = 1. Тогда T(n) есть O(n2) по определению Пример 3. T(n) = c. Говорят: T(n) есть O(1).

Слайд 22


Асимптотический анализ: O() Распространенная ошибка “Лучшим для моего алгоритма является случай n=1, т.к. при этом алгоритм наиболее быстр” – НЕКОРРЕКТНО! O() описывает характер роста по мере стремления n к  Лучшим случаем называют такой, при котором на обработку входных данных размера n тратится наименьшее время по сравнению с прочими данными того же размера
Описание слайда:
Асимптотический анализ: O() Распространенная ошибка “Лучшим для моего алгоритма является случай n=1, т.к. при этом алгоритм наиболее быстр” – НЕКОРРЕКТНО! O() описывает характер роста по мере стремления n к  Лучшим случаем называют такой, при котором на обработку входных данных размера n тратится наименьшее время по сравнению с прочими данными того же размера

Слайд 23


Асимптотический анализ: O() Распространенная ошибка Часто худший случай путают с верхней границей Верхняя граница описывает характер роста по мере стремления n к  Худшим случаем называют такой, при котором на обработку входных данных размера n тратится наибольшее время по сравнению с прочими данными того же размера
Описание слайда:
Асимптотический анализ: O() Распространенная ошибка Часто худший случай путают с верхней границей Верхняя граница описывает характер роста по мере стремления n к  Худшим случаем называют такой, при котором на обработку входных данных размера n тратится наибольшее время по сравнению с прочими данными того же размера

Слайд 24


Асимптотический анализ: () Определение Говорят, что неотрицательная функция f(n) есть (g(n)), если существуют константы c>0 и n0>0, такие что f(n) ≥ cg(n) для любых n > n0. Смысл Для всех достаточно больших входных данных (n>n0), алгоритм всегда выполняется более, чем за cg(n) шагов Нижняя граница Оценка (g(n)) задает нижнюю асимптотическую оценку роста функции f(n) и определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя
Описание слайда:
Асимптотический анализ: () Определение Говорят, что неотрицательная функция f(n) есть (g(n)), если существуют константы c>0 и n0>0, такие что f(n) ≥ cg(n) для любых n > n0. Смысл Для всех достаточно больших входных данных (n>n0), алгоритм всегда выполняется более, чем за cg(n) шагов Нижняя граница Оценка (g(n)) задает нижнюю асимптотическую оценку роста функции f(n) и определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя

Слайд 25


Асимптотический анализ: () Пример. T(n) = c1n2 + c2n. c1n2 + c2n ≥ c1n2 для любых n > 1 T(n) ≥ cn2 для c = c1 и n0 = 1 Таким образом, T(n) есть (n2) по определению Из всех нижних границ интересна наибольшая
Описание слайда:
Асимптотический анализ: () Пример. T(n) = c1n2 + c2n. c1n2 + c2n ≥ c1n2 для любых n > 1 T(n) ≥ cn2 для c = c1 и n0 = 1 Таким образом, T(n) есть (n2) по определению Из всех нижних границ интересна наибольшая

Слайд 26


Асимптотический анализ: () Определение Говорят, что неотрицательная функция f(n) есть (g(n)), если существуют константы c1>0, c2>0 и n0>0, такие что c1g(n) ≤ f(n) ≤ c2g(n) для любых n > n0. Функция f(n) есть (g(n)), если она одновременно есть (g(n)) и O(g(n)) Смысл Асимптотическое равенство (с точностью до константы) Полностью описывает характер роста функции
Описание слайда:
Асимптотический анализ: () Определение Говорят, что неотрицательная функция f(n) есть (g(n)), если существуют константы c1>0, c2>0 и n0>0, такие что c1g(n) ≤ f(n) ≤ c2g(n) для любых n > n0. Функция f(n) есть (g(n)), если она одновременно есть (g(n)) и O(g(n)) Смысл Асимптотическое равенство (с точностью до константы) Полностью описывает характер роста функции

Слайд 27


Асимптотический анализ Правила упрощения Транзитивность Если f(n) есть O(g(n)) и g(n) есть O(h(n)), то f(n) есть O(h(n)) Игнорирование констант Если f(n) есть O(kg(n)) для любой константы k > 0, то f(n) есть O(g(n)) Отбрасывание членов низких порядков Если f1(n) есть O(g1(n)) и f2(n) есть O(g2(n)), то (f1 + f2)(n) есть O(max(g1(n), g2(n))) Мултипликативность Если f1(n) есть O(g1(n)) и f2(n) есть O(g2(n)), то f1(n)f2(n) есть O(g1(n)g2(n))
Описание слайда:
Асимптотический анализ Правила упрощения Транзитивность Если f(n) есть O(g(n)) и g(n) есть O(h(n)), то f(n) есть O(h(n)) Игнорирование констант Если f(n) есть O(kg(n)) для любой константы k > 0, то f(n) есть O(g(n)) Отбрасывание членов низких порядков Если f1(n) есть O(g1(n)) и f2(n) есть O(g2(n)), то (f1 + f2)(n) есть O(max(g1(n), g2(n))) Мултипликативность Если f1(n) есть O(g1(n)) и f2(n) есть O(g2(n)), то f1(n)f2(n) есть O(g1(n)g2(n))

Слайд 28


Асимптотический анализ Пример 1
Описание слайда:
Асимптотический анализ Пример 1

Слайд 29


Асимптотический анализ Пример 3
Описание слайда:
Асимптотический анализ Пример 3

Слайд 30


Асимптотический анализ Пример 4
Описание слайда:
Асимптотический анализ Пример 4

Слайд 31


Асимптотический анализ Пример 5
Описание слайда:
Асимптотический анализ Пример 5

Слайд 32


Бинарный поиск Идея алгоритма Временная сложность алгоритма
Описание слайда:
Бинарный поиск Идея алгоритма Временная сложность алгоритма

Слайд 33


Бинарный поиск Возможно ли ускорить линейный алгоритм поиска элемента в массиве? ((n)) Да, если массив упорядочен Наличие порядка позволяет использовать принцип «разделяй и властвуй»: на каждом шаге уменьшая вдвое размер решаемой задачи Бинарный поиск – реализация стратегии «разделяй и властвуй» в чистом виде
Описание слайда:
Бинарный поиск Возможно ли ускорить линейный алгоритм поиска элемента в массиве? ((n)) Да, если массив упорядочен Наличие порядка позволяет использовать принцип «разделяй и властвуй»: на каждом шаге уменьшая вдвое размер решаемой задачи Бинарный поиск – реализация стратегии «разделяй и властвуй» в чистом виде

Слайд 34


Бинарный поиск На каждом шаге центральный элемент A[m] проверяется на совпадение с искомым K Если A[m] = K, конец алгоритма Если A[m] < K, то далее решается задача поиска в подмассиве A[m]…A[n]? иначе – в подмассиве A[1]…A[m]
Описание слайда:
Бинарный поиск На каждом шаге центральный элемент A[m] проверяется на совпадение с искомым K Если A[m] = K, конец алгоритма Если A[m] < K, то далее решается задача поиска в подмассиве A[m]…A[n]? иначе – в подмассиве A[1]…A[m]

Слайд 35


Бинарный поиск Код
Описание слайда:
Бинарный поиск Код

Слайд 36


Асимптотический анализ различных управляющих конструкций Цикл while анализируется так же как и for Условный оператор if оценивается по наиболее сложной ветви then/else Вероятность срабатывания ветвей не должна зависеть от n Оператор ветвления switch оценивается по наиболее сложной ветви case Вероятность срабатывания ветвей не должна зависеть от n Сложность вызова подпрограммы равна сложности подпрограммы
Описание слайда:
Асимптотический анализ различных управляющих конструкций Цикл while анализируется так же как и for Условный оператор if оценивается по наиболее сложной ветви then/else Вероятность срабатывания ветвей не должна зависеть от n Оператор ветвления switch оценивается по наиболее сложной ветви case Вероятность срабатывания ветвей не должна зависеть от n Сложность вызова подпрограммы равна сложности подпрограммы

Слайд 37


Асимптотический анализ сложности задач Анализ задачи = анализ классов алгоритмов Верхняя граница: верхняя граница сложности наилучшего из известных алгоритмов решения задачи Нижняя граница: нижняя граница для всех известных алгоритмов решения задачи
Описание слайда:
Асимптотический анализ сложности задач Анализ задачи = анализ классов алгоритмов Верхняя граница: верхняя граница сложности наилучшего из известных алгоритмов решения задачи Нижняя граница: нижняя граница для всех известных алгоритмов решения задачи

Слайд 38


Асимптотический анализ сложности задач Пример Нет смысла говорить о верхних/нижних границах, если известно точное количество операций Пример неточных знаний о задаче: сортировка 1. Сложность ввода/вывода: (n). 2. Пузырьковая сортировка или вставками: O(n2). 3. Более эффективные методы (Quicksort, Mergesort, Heapsort, и т.д.): O(n log n). 4. Для некоторых типов данных существуют методы со сложностью O(n).
Описание слайда:
Асимптотический анализ сложности задач Пример Нет смысла говорить о верхних/нижних границах, если известно точное количество операций Пример неточных знаний о задаче: сортировка 1. Сложность ввода/вывода: (n). 2. Пузырьковая сортировка или вставками: O(n2). 3. Более эффективные методы (Quicksort, Mergesort, Heapsort, и т.д.): O(n log n). 4. Для некоторых типов данных существуют методы со сложностью O(n).

Слайд 39


Асимптотический анализ: несколько параметров Упорядочить по популярности C значений пикселов на изображении, содержащем P пикселов Если в качестве размера данных использовать P, то время работы есть (P log P) Более точно: (P + C log C)
Описание слайда:
Асимптотический анализ: несколько параметров Упорядочить по популярности C значений пикселов на изображении, содержащем P пикселов Если в качестве размера данных использовать P, то время работы есть (P log P) Более точно: (P + C log C)

Слайд 40


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

Слайд 41


Баланс «затраты памяти»/«затраты времени» Временные затраты алгоритма могут быть понижены, если повысить расход памяти и наоборот: Жертвуя временем, можно сэкономить память Принцип баланса «время»/«дисковое пространство»: Чем меньше затраты дискового пространства, тем быстрее программа
Описание слайда:
Баланс «затраты памяти»/«затраты времени» Временные затраты алгоритма могут быть понижены, если повысить расход памяти и наоборот: Жертвуя временем, можно сэкономить память Принцип баланса «время»/«дисковое пространство»: Чем меньше затраты дискового пространства, тем быстрее программа

Слайд 42


Вопросы? Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший, средний и лучший случаи Что ускорять: компьютер или алгоритм? Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и пространственная сложность Бинарный поиск Идея алгоритма Временная сложность алгоритма
Описание слайда:
Вопросы? Эффективность алгоритмов Эффективность алгоритмов и ее измерение Временная сложность алгоритма в зависимости от размера задачи Худший, средний и лучший случаи Что ускорять: компьютер или алгоритм? Асимптотический анализ алгоритмов Цели асимптотического анализа О-символика Примеры асимптотического анализа алгоритмов Асимптотическая сложность задач Временная и пространственная сложность Бинарный поиск Идея алгоритма Временная сложность алгоритма

Скачать

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