М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 46
Текст из файла (страница 46)
Предположим, например, что нас интересует количество элементов, необходимое для сложения двух и-битовых чисел. Точное вычисление этого количества только затемняет обшую картину. В самом деле, пусть некоторый алгоритм требует для этого сложения 24п+ 2[1об и] + 16 элементов; в предельном случае задач большого размера единственное слагаемое, которое играет роль, это 24п. Далее, мы не обращаем внимание на постоянные сомножители, поскольку их значение для анализа алгоритмов второстепенно. Существенное поведение алгоритма можно описать, сказав, что число требуемых операций примерно пропорционально п, где п — количество битов в складываемых числах.
Есть три основных асимптотических обозначений. Обозначение О («О большое») используется для указания веряиоя оценок функций. Пусть Дп) и д(п) — функции на целых неотрицательных числах. Мы говорим «~(п) принадлежит классу функций 0(д(п))», если существуют такие константы с и по, что для всех и, ббльших по, выполняется'неравенство Дп) < сд(п). Тем самым для достаточно больших и функция д(п) является верхней 3.2. Анализ вычислительных задач 183 оценкой для у(п), с точностью до несущественногц постоянного множителя. Обозначения с «О» особенно полезны при изучении поведения конкрептнмз алгоритмов в худшем случае, когда нам часто хватает верхней оценки ресурсов, потребляемых алгоритмом. При изучении поведения целого к«асса алгоритмов (например, алгоритмов умножения двух чисел) интересно найти нижние оценки требуемых ресурсов.
При этом используются обозначения с буквой Й («Й большое»). Говорят, что функция 7(п) принадлежнг Й(д(п)), если существуют такие числа с и по, что сд(п) <ч 7"(и) при всех и, ббльших по. Другими словами при достаточно больших и функция д(п) является нижней оценкой для т(п) с точностью до несущественного постоянного множителя. Наконец, обозначения с буквой 6 («9 большое») используются, когда нужно сказать, что асимптотически т (и) ведет себя так же, как д(п), с точностью до несущественных постоянных множителей. Мы говорим, что 1(п) принадлежит ст(д(п)), если она одновременно принадлежит классам 0(д(п)) и Й(д(п)).
Асимптаотаические обозначения: промеры Рассмотрим несколько простых примеров асимптотических обозначений. Функция 2п принадлежит 0(тР), поскольку 2п < 2тР для всех положительных и. Функция 2" принадлежит Й(тР), поскольку тР < 2" для достаточно больших и. Наконец, функция 7тР + ~/й 1о8 и есть 9(тР), поскольку 7пз < 7пз+ ~/й1обп < 8пз при всех достаточно больших и. В следующих упражнениях вы познакомитесь с элементарными свойствами асимптотическвх обозначений, благодаря которым они являются полезным инструментом при анализе алгоритмов. Упражнение 3.9. Докажите, что 7" (п) принадлежит 0(д(п)) тогда и только тогда, когда д(п) принадлежит ЙЩп)).
Выведите отсюда, что 7(п) принадлежит ст(д(п)) тогда и только тогда, когда д(п) принадлежит ст(7(п)). Упражнение 3.10. Пусть д(п) — многочлен степени й. Покатквте, что д(п) првнадлежлт 0(п') при всех 1 > й. Упражнение 3.11. Покажите, что 1обп принадлежит 0(п") при всех й ) О. Упражнение 3.12 (и"'к" суперполиномивльна).
Покажите, что и" принадлежит 0(п'«з") для любого й, но пток" никогда не принадлежит 0(пь). Упражнение 3.13 (пт«е" субэкспоненциальна). Покажите, что с" принадлежит Й(пме") для любого с ) 1, но птое" никогда не принадлежит Й(с"). Упражнение 3.14. Пусть е(п) принадлежит 0(т'(п)) и д(п) принадлежит 0(Л(п)). Покажите, что е(п)д(п) принадлежит 0(7(п)Л(п)).
Примером использования асимптотических обозначений при оценке компьютерных ресурсов является следующее простое приложение к задаче сортировки списка из и слов в алфавитном порядке. Многие алгоритмы сортировки основаны на операции «сравнение и обмен»: два элемента в и-элементном списке сравниваются и, если они идут в неправильном порядке, меняются местами. Если зта операция сравнения с обменом — единственное, что мы можем делать 184 Глава 3.
Введение в информатику со списком, то сколько таких операций нужно, чтобы гарантировать, что список отсортирован? Простой алгоритм сортировки, основанный на сравнении и обмене, выглядит так (команда сошраге-апа-виар(),К) сравнивает записи с номерами у и Й и меняет их местами, если они идут в неверном порядке): Хог 3' 1 со и-1 Хог К=3+1 со и сошраге-апа-виар(),К) епа К й3 Ясно, что этот алгоритм правильно сортирует список из и слов в алфавитном порядке. Заметим, что число операций «сравнение и обмен», выполняемых алгоритмом, равно (и — 1) + (и — 2) +... + 1 = п(п — 1)/2.
Таким образом, число этих операций есть 9(пэ). Можно ли обойтись меньшим количеством? Оказывается, что да. Известны алгоритмы, например «Ьеарэогг» (сортировка с помощью кучи), использующие 0(п )они) сравнений. Далее в упражнении 3.15 вы покажете с помощью несложного подсчета, что любой алгоритм, основанный на операции «сравнение и обмен», использует й(п 1оя п) этих операций. Таким образом, сортировка, вообще говоря, требует 9(п 1оя и) сравнений. Упражнение 3.1б (нижние оценки для сортировки, основанной на сравнении и обмене). Пусть и-элементный список подвергается сортировке с помощью некоторой последовательности операций «сравнение и обмен». Расположить элементы в списке можно и! способами. Покажите, что после й операций «сравнение и обмен» список будет отсортирован для не более чем 2ь начальных расстановок.
Выведите отсюда, что для того, чтобы отсортировать способом «сравнение и обмен» любую исходную расстановку, необходимо й(п 1оя п) операций. 3.2.2 Сложность вычислений Мысль о том, что не существует алгоритма, реишющего эпщ задачу, — что есть что-то фундаментальное, что никогда не изменится — эта мысль мне нравится. Стивен Кук Иногда это хорошо, что некоторые вещи невоэмоэюны. Я рад, чпю есть много вещей, но«порыв никто не сможет сделать со мной. Леонид Левин 3.2. Анализ вычислительных задач 185 Не следует удивляться тпому, чтпо наш выбор полинвмиальных аггоритмов в качестпве формализации неформального понятия твткчисзение, эффектпивное на практике», подвержен критпике со всех сторон. (...) В конечном счете наш довод в пользу этого выбора должен звучать тпак: если принятпь полиномиальность в худтиезз случае за критерий эффектпивностпи, то получаетпся элегантная и полезная теория, котпорая говоритп нечто осмысленное о практических вычислениях и котпорая была бы невозмоэкна без этого упротцения.
Кристос Пападимитриу Сколько времени и памяти нужно для данного вычисления? Во многих случаях это самые важные вопросы, которые можно задать о вычислительной задаче. Задачи вроде сложения и умножения чисел считаются эффективно разрешимыми, поскольку у нас есть быстрые алгоритмы для сложения и умнотцения, которые в процессе выполнения используют мало памяти. Для многих других задач быстрые алгоритмы неизвестны и тем самым эти задачи по существу неразрешимы не потому, что мы не можем найти разрешающий их алгоритм, а потому, что для всех известных алгоритмов требуется настолько большие объемы времени и памяти, что это делает их практически бесполезными. Теория сложности вычислений изучает, сколько времени и памяти необходимо для решения вычислительных задач.
Задача этой теории — дать нижние зцгнки для объема ресурсов, потребляемых наилучшим возможным алгоритмом для решения данной задачи (даже если такой алгоритм в явном виде не известен). В этом и двух следующих разделах дается обзор теории сложности вычислений, ее основных понятий и некоторых вз наиболее важных результатов.
Отметим, что теория сложности вычислений в каком-то смысле дополяительна к разработке алгоритмов; в идеале для наиболее эффективных алгоритмов, которые мы можем создать, будут в точности достигаться нижние оценки, полученные в рамках теории сложности вычислений. К сожалению, часто дело обстоит иначе. Как уже отмечали, в этой книге мы не будем глубоко рассматривать разработку классических алгоритмов. При формулировке утверждений теории сложности вычислений возникает одна трудность: для решения одной и той же задачи на разных вычислительных моделях может быть нужен разный объем ресурсов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
