|
ПРЯМО
УГОЛЬНИКОВ
|
0(Л»<з у,)
|
' QC*)
|
|
ОСА
|
ОМ>
м
|
1б
|
О.Л с
|
1.6 с
|
6 А с
|
25.6 с
|
66301 леи*
|
2S6
|
0-1 с
|
25Л с
|
ЗА мин
|
1.2 ч
|
%,6*1<Г леи*
|
10Z4
|
1.0 с
|
1.7 е
|
1? мин
|
1.2. дня
|
SAxl^’Vem
|
иже показано, сколько времени потребуется для построения сетки с остальными алгоритмами, от самого быстрого до самого медленного:
Существуют и другие варианты времени выполнения, но эти пять встречаются чаще всего.
Помните, что эта запись является упрощением. На практике «О-большое» не удается легко преобразовать в количество операций с такой точностью, но пока нам хватит и этого. Мы еще вернемся к «О-болыиому» в главе 4, после рассмотрения еще нескольких алгоритмов. А пока перечислим основные результаты:
Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций.
По сути формула описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.
Время выполнения алгоритмов выражается как «О-большое».
Время выполнения 0(log п) быстрее 0(п), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.
Упражнения
Приведите время выполнения «О-большое» для каждого из следующих сценариев.
Известна фамилия, нужно найти номер в телефонной книге.
Известен номер, нужно найти фамилию в телефонной книге. (Подсказка: вам придется провести поиск по всей книге!)
Нужно прочитать телефоны всех людей в телефонной книге.
Нужно прочитать телефоны всех людей, фамилии которых начинаются с буквы «А». (Вопрос с подвохом! В нем задействованы концепции, которые более подробно рассматриваются в главе 4. Прочитайте ответ — скорее всего, он вас удивит!)
Задача о коммивояжере
Наверное, после прочтения предыдущего раздела вы подумали: «Уж мне-то точно не попадется алгоритм с временем 0(п/)» Ошибаетесь, и я это сейчас докажу! Мы рассмотрим алгоритм с очень, очень плохим временем выполнения. Это известная задача из области теории вычислений, в которой время выполнения растет с просто ужасающей скоростью, и некоторые очень умные люди считают, что с этим ничего не поделать. Она называется задачей о коммивояжере.
Э го коммивояжер.
Он должен объехать 5 городов.
Коммивояжер хочет побывать в каждом из 5 городов так, чтобы при этом проехать минимальное общее расстояние. Одно из возможных решений: нужно перебрать все возможные комбинации порядка объезда городов.
Все расстояния суммируются, после чего выбирается путь с кратчайшим расстоянием. Для 5 городов можно создать 120 перестановок, поэтому решение задачи для 5 городов потребует 120 операций. Для 6 городов количество операций увеличивается до 720 (существуют 720 возможных перестановок). А для 7 городов потребуется уже 5040 операций!
Г0Р0ЛА
|
ОПЕРАЦИИ
|
б
|
Ч-2Ф
|
?
|
ьрьФ
|
Ь
|
|
". • •
|
! • • ’
|
~16>
|
|
|
2^5 2р2?6Лр\-21'Н
|
Количество операций стремительно растет
В общем случае для вычисления результата при п элементах потребуется п! (и-факториал) операций. А значит, время выполнения составит 0(п!) (такое время называется факториальным). При любом сколько-нибудь серьезном размере списка количество операций будет просто огромным. Скажем, если вы попытаетесь решить задачу для 100+ городов, сделать это вовремя не удастся — Солнце погаснет раньше.
Какой ужасный алгоритм! Значит, коммивояжер должен найти другое решение, верно? Но у него ничего не получится. Это одна из знаменитых нерешенных задач в области теории вычислений. Для нее не существует известного быстрого алгоритма, и ученые считают, что найти более эффективный алгоритм для этой задачи в принципе невозможно. В лучшем случае для нее можно поискать приближенное решение; за подробностями обращайтесь к главе 10.
И последнее замечание: если у вас уже есть опыт программирования, почитайте о бинарных деревьях поиска! Эти структуры данных кратко описаны в последней главе.
Шпаргалка
Бинарный поиск работает намного быстрее простого.
Время выполнения 0(log п) быстрее 0(п), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.
Скорость алгоритмов не измеряется в секундах.
Время выполнения алгоритма описывается ростом количества операций.
Время выполнения алгоритмов выражается как «О-болыное».
С
В этой главе
Вы познакомитесь с массивами и связанными списками — двумя основными структурами данных, которые используются буквально везде. Мы уже использовали массивы в главе 1 и будем использовать их почти в каждой главе книги. Массивы чрезвычайно важны, уделите им внимание! Впрочем, иногда вместо массива лучше воспользоваться связанным списком. В этой главе объясняются плюсы и минусы обеих структур данных, чтобы вы могли решить, какой вариант лучше подходит для вашего алгоритма.
Вы изучите свой первый алгоритм сортировки. Многие алгоритмы работают только с отсортированными данными. Помните бинарный поиск? Он применяется только к предварительно отсортированному списку. В большинстве языков существуют встроенные алгоритмы сортировки, так что вам редко приходится писать свою версию «с нуля». Однако алгоритм сортировки выбором поможет перейти к алгоритму быстрой сортировки, описанному в следующей главе. Алгоритм быстрой сортировки очень важен, и вам будет проще разобраться в нем, если вы уже знаете хотя бы один алгоритм сортировки.
ортировка выбором
Do'stlaringiz bilan baham: |
