lection19.10
.pdf
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Временная и емкостная сложность алгоритмов
В.А. Дель, студент гр. 529-1
Томский государственный университет систем управления и радиоэлектроники
Кафедра комплексной информационной безопасности электронно-вычислительных систем
19 октября 2013 г.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
1 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
1 Вступление
2 Временная сложность
3 O-нотация
4 Порядок роста функций
5 Емкостная сложность
6 Алгоритмы
7 Инструменты
8 Философия Промышленное программирование Как решать задачи Как тренироваться
9 Ссылки и литература
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
2 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Вступление
Every problem has a simple, fast but wrong solution.
(c)
Для каждой задачи существуют временные и емкостные ограничения.
Ограничение по времени: 2 секунды.
Ограничение по памяти: 256 мегабайт.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
3 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Цель
Научиться создавать и сравнивать решения по
количеству требуемого времени;
количеству требуемой памяти.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
4 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Временная сложность
Пусть имеется задача ¾A + B¿. Решение очевидно:
Сколько потребуется операций?
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
5 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Временная сложность
Количество операций никак не меняется от различных входных данных.
Ответ: O(1).
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
6 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
O-нотация
Пусть задача имеет входные данные, зависящие от параметров N1; N2; :::; Nn.
Тогда сложностью алгоритма назовем порядок роста количества операций, требуемых для решения данной задачи.
Обозначение: O(f (N1; N2; :::; Nn)).
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
7 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Пример
Дана функция от двух целочисленных переменных:
f (x; y) = x2 + x y3 + x4 x3 + 6y:
Найти ее максимальное значение при следующих ограничениях:
1 x N,
1 y M,
где 1 N 1000, а 1 M 2000.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
8 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Решение
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
9 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Оценка сложности
Перебираем все возможные значения x.
Для каждого x перебираем все возможные значения y.
Для каждой пары (x; y) считаем значение функции.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
10 / 31 |