Сложность алгоритмов.

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

Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень)

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

Ключевые слова:

• временная сложность	
• пространственная сложность	
• время работы алгоритма	
• асимптотическая сложность
• линейная сложность
• квадратичная сложность

Большинство задач могут быть решены по-разному, с помощью разных алгоритмов. Поэтому возникает вопрос: как выбрать лучший? И ещё один важный вопрос — способен ли современный компьютер за приемлемое время найти решение задачи? Например, в игре в шахматы возможно лишь конечное количество позиций и, следовательно, только конечное количество различных партий. Значит, теоретически можно перебрать все возможные партии и выяснить, кто побеждает при правильной игре — белые или чёрные. Однако количество вариантов настолько велико, что современные компьютеры не могут выполнить такой перебор за приемлемое время.

Что мы хотим от алгоритма? Во-первых, чтобы он работал как можно быстрее. Во-вторых, чтобы объём необходимой памяти был как можно меньше. В-третьих, чтобы он был как можно более прост и понятен, что позволяет легче отлаживать программу. К сожалению, эти требования противоречивы, и в серьёзных задачах редко удаётся найти алгоритм, который был бы лучше остальных по всем показателям.

Часто говорят о временной сложности алгоритма (быстродействии) и пространственной сложности, которая определяется объёмом необходимой памяти.

Временем работы алгоритма называется количество элементарных операций T, выполненных исполнителем.

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

Как правило, величина Т будет существенно зависеть от объёма исходных данных: поиск в списке из 10 элементов завершится гораздо быстрее, чем в списке из 10000 элементов. Поэтому сложность алгоритма обычно связывают с размером входных данных N и определяют как функцию T(N). Например, для алгоритмов обработки массивов в качестве размера N используют длину массива. Функция T(N) называется временной сложностью алгоритма.

Временная сложность агоритма определяется функцией T(N) = 2N³. Во сколько раз увеличится время работы алгоритма, если размер данных N увеличится в 10 раз?

Пространственная сложность — это зависимость объёма занимаемой памяти от размера данных N. Для ускорения работы некоторых алгоритмов нужно использовать дополнительную память, которая может быть намного больше, чем память для хранения исходных данных.

Для быстрой сортировки массива из N элементов с помощью алгоритма Семёна требуется N вспомогательных массивов, каждый из которых содержит N элементов. Как изменится объём нужной дополнительной памяти, если N увеличится в 10 раз?

Поскольку память постоянно дешевеет, а быстродействие компьютеров растёт медленно, более важна временная сложность алгоритмов. Пространственную сложность мы дальше рассматривать не будем.

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

Рассмотрим алгоритмы выполнения различных операций с массивом А длины N, который может быть объявлен в программе так:

целтаб А[1:N] var A: array[1..N] of integer;

Пример 1. Вычислить сумму значений первых трёх элементов массива (при N ? 3).

Решение этой задачи содержит всего один оператор:

Sum:=А[1]+А[2]+А[3];

Этот алгоритм включает две операции сложения и одну операцию записи значения в память, поэтому его сложность T(N) = 3 не зависит от размера массива вообще.

Вычислите количество операций (считая сравнения и присваивание значений переменным) при выполнении фрагмента программы:

Пример 2. Вычислить сумму значений всех элементов массива.

В этой задаче уже не обойтись без цикла:

Здесь выполняется N операций сложения и N + 1 операция записи в память, поэтому его сложность T(N) = 2N + 1 возрастает линейно с увеличением длины массива.

Вычислите количество операций при выполнении фрагмента программы:

Пример 3. Отсортировать все элементы массива по возрастанию методом выбора. Напомним, что метод выбора предполагает поиск на каждом шаге минимального из оставшихся неупорядоченных значений (здесь i, j, nMin и с — целочисленные переменные):

Подсчитаем отдельно количество сравнений и количество перестановок. Количество сравнений элементов массива не зависит от данных и определяется числом шагов внутреннего цикла:

Здесь использована формула для суммы первых N — 1 членов арифметической прогрессии.

На каждом шаге внешнего цикла происходит перестановка двух элементов, общее количество перестановок равно Т_n( N) = N -1, т. е. сложность по перестановкам — линейная.

Определите количество операций при вычислении суммы значений элементов квадратной матрицы А размером N х N (здесь i, j и Sum — целочисленные переменные):

По результатам этих примеров можно сделать выводы:

• простой цикл, в котором количество шагов пропорционально N, — это алгоритм линейной сложности;
• вложенный цикл, в котором количество шагов внешнего и внутреннего цикла пропорционально N, — это алгоритм квадратичной сложности.

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

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

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
N²	10 мс
N³	0,001 с
2^N	10¹³ лет

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

Выводы

• Временем работы алгоритма называется количество элементарных операций Т, выполненных исполнителем.
• Временная сложность алгоритма обычно зависит от объёма исходных данных N, например от размера массива.
• Пространственная сложность — это объём памяти, необходимой для работы алгоритма.
• Простой цикл, в котором количество шагов пропорционально N, — это алгоритм линейной сложности.
• Вложенный цикл, в котором количество шагов внешнего и внутреннего цикла пропорционально N, — это алгоритм квадратичной сложности.
• Алгоритм имеет асимптотическую сложность 0(f(N)), если найдётся такая постоянная с, что, начиная с некоторого N = N₀, выполняется условие T(N) ? с • f(N).
• Линейная сложность означает, что при увеличении размера массива в К раз количество операций увеличивается примерно в К раз.
• Квадратичная сложность означает, что при увеличении размера массива в К раз количество операций увеличивается примерно в К² раз.

Нарисуйте в тетради интеллект-карту этого параграфа.

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

1. Какие критерии используются для оценки алгоритмов?
2. Почему скорость работы алгоритма оценивается не временем выполнения, а количеством элементарных операций?
3. Как учитывается размер данных при оценке быстродействия алгоритма?
4. В каких случаях алгоритм, имеющий асимптотическую сложность 0(N²), может работать быстрее, чем алгоритм с асимптотической сложностью 0(N)?
5. Выполните по указанию учителя задания в рабочей тетради.

Подготовьте сообщение

«Задача коммивояжёра»

Оглавление

§21. Матрицы (двумерные массивы).

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

§23. Как разрабатывают программы?