Урок 39
§22. Сложность алгоритмов

Содержание урока

Как сравнивать алгоритмы?

Примеры вычисления сложности

Что такое асимптотическая сложность?

Выводы

Вопросы и задания

Что такое асимптотическая сложность?

Допустим, что нужно сделать выбор между несколькими алгоритмами, которые имеют разную сложность. Какой из них лучше (работает быстрее)? Оказывается, для этого необходимо знать размер массива данных, которые нужно обрабатывать. Сравним, например, три алгоритма, сложность которых

T₁(N) = 10000 • N, T₂(N) = 100 • N² и T₃(N) = N³.

Построим эти зависимости на графике (рис. 4.5). При N ≤ 100 получаем Т₃(N) < T₂(N) < T₁N), при N = 100 количество операций для всех трёх алгоритмов совпадёт, а при больших N имеем Т₃(N) > T₂(N) > T₁N).

Рис. 4.5

Обычно в теоретической информатике при сравнении алгоритмов используется их асимптотическая сложность, т. е. скорость роста количества операций при больших значениях N.

Запись 0(N) (читается «О большое от N») обозначает линейную сложность алгоритма. Это значит, что, начиная с некоторого значения N = N₀, количество операций будет меньше, чем с•N, где с — некоторая постоянная:

T(N)≤c•N для N≥N₀.

При увеличении размера данных в 10 раз объём вычислений алгоритма с линейной сложностью увеличивается тоже примерно в 10 раз.

Пусть, например, T(N) = 2N - 1, как в алгоритме поиска суммы значений элементов массива. Очевидно, что при этом T(N) ≤ 2N для всех N ≥ 1, поэтому алгоритм имеет линейную сложность.

Определите любые подходящие значения с и N₀, такие что T(N) ≤ с•N для N ≥ N₀, для алгоритмов с линейной асимптотической сложностью:

a) T(N) = 12N - 8;

б) T(N) = 7N + 5.

Многие известные алгоритм имеют квадратичную сложность 0(N²). Это значит, что сложность алгоритма при больших N меньше, чем с•N²:

T(N)≤c•N² для N≥N₀.

Если размер данных увеличивается в 10 раз, то количество операций (и время выполнения такого алгоритма) увеличивается примерно в 100 раз. Пример алгоритма с квадратичной сложностью — сортировка методом выбора, для которой число сравнений

Определите любые подходящие значения с и N₀, такие что T(N) ≤ с•N² для N ≥ N₀, для алгоритмов с квадратичной асимптотической сложностью:

a) T(N) = 5N² - 3N - 2;

б) T(N) = 7N² - 3N - 5.

Алгоритм имеет асимптотическую сложность 0(f(N)), если найдется такая постоянная с, что, начиная с некоторого N = N₀, выполняется условие T(N)≤c•f(N).

Это значит, что график функции с•f(N) проходит выше, чем график функции T(N), по крайней мере, при N≥N₀ (рис. 4.6).

Рис. 4.6

Если количество операций не зависит от размера данных, то говорят, что асимптотическая сложность алгоритма 0(1), т. е. количество операций меньше некоторой постоянной при любых N.

Существует также немало алгоритмов с кубической сложностью 0(N³). При больших значениях N алгоритм с кубической сложностью требует большего количества вычислений, чем алгоритм со сложностью 0(N²), а тот, в свою очередь, работает дольше, чем алгоритм с линейной сложностью. Однако при небольших значениях N всё может быть наоборот, это зависит от постоянной с для каждого из алгоритмов.

Известны и алгоритмы, для которых количество операций растёт быстрее, чем любой многочлен, например как 0(2^N) или 0(N!), где N! обозначает факториал числа N — произведение всех натуральных чисел от 1 до N : N! = 1 • 2 • 3 •... • N. Такие алгоритмы встречаются чаще всего в задачах поиска оптимального (наилучшего) варианта, которые решаются только методом полного перебора. Самая известная задача такого типа — это задача коммивояжёра (бродячего торговца), который должен посетить по одному разу каждый из указанных городов и вернуться в начальную точку. Для него нужно выбрать маршрут, при котором стоимость поездки (или общая длина пути) будет минимальной.

В таблице 4.1 показано примерное время работы алгоритмов, имеющих разную временную сложность, при N = 100 на компьютере с быстродействием 1 миллиард операций в секунду.

Таблица 4.1

T(N)	Время выполнения
N	100 нc
N2	10 мс
N3	0,001 с
2N	1013 лет

Юный программист Григорий поспорил с учителем, что сможет к завтрашнему уроку с помощью компьютера решить сложную задачу перебора вариантов. Дома он определил временную сложность алгоритма: T(N) = 2^N. Для какого наибольшего значения N сможет Григорий решить задачу за сутки, если его компьютер выполняет 1 миллиард операций в секунду?

Следующая страница Выводы

Cкачать материалы урока