Чистыйкод дляпродолжающи х
 Скачать 7.85 Mb.
|
|
Порядки нотации «О-большое» Нотация «О-большое» обычно определяет несколько порядков сложности. Ниже эти порядки перечислены по возрастанию (сначала указаны низкие порядки, при которых код с ростом объема данных замедляется в наименьшей степени, а в кон- це — высокие порядки с наибольшим замедлением). 1. O(1), постоянное время (самый низкий порядок). 2. O(log n), логарифмическое время. 3. O(n), линейное время. 4. O(n log n), время N-Log-N. 5. O(n 2 ), полиномиальное время. 6. O(2 n ), экспоненциальное время. 7. O(n!), факториальное время (наивысший порядок). Обратите внимание на форму записи порядка «О-большое»: буква O в верхнем ре- гистре, за ней следует пара круглых скобок с описанием порядка. Буква n в скобках представляет размер входных данных, с которыми работает код. Порядки нотации «О-большое» 271 Чтобы использовать нотацию «О-большое», не обязательно понимать точный мате- матический смысл таких терминов, как «логарифмическое» или «полиномиальное». Все порядки я более подробно опишу в следующем разделе, а пока ограничусь простым обозначением. O(1) и O(log n) — быстрые алгоритмы. O(n) и O(n log n) — неплохие алгоритмы. O(n 2 ), O(2 n ) и O(n!) — медленные алгоритмы. Конечно, можно найти и контрпримеры, но в общем случае эту классифи- кацию можно считать хорошей. Здесь перечислены не все порядки нотации «О-большое», а только самые распространенные. Рассмотрим примеры задач для каждого из них. Книжная полка как метафора порядков «О-большое» В следующих примерах нотации «О-большое» я продолжу использовать метафору с книжной полкой. В описаниях n обозначает количество книг на полке, а порядок «О-большое» описывает, как растет время выполнения различных операций с уве- личением количества книг. O(1), постоянное время Если вы проверяете, пуста ли книжная полка, это операция с постоянным време- нем. Неважно, сколько книг на полке; вы с первого взгляда определите, есть ли на ней книги. Их количество может изменяться, но время выполнения останется постоянным, потому что, если вы видите на полке хотя бы одну книгу, дальше можно не проверять. Значение n не влияет на скорость выполнения задачи, по- этому n не входит в обозначение O(1). Также постоянное время иногда записы- вается в виде O(c). O(log n), логарифмическое время Логарифм является операцией, обратной по отношению к возведению в степень; результат 2 4 , или 2 × 2 × 2 × 2, равен 16, тогда как логарифм log 2 (16) (читается «логарифм 16 по основанию 2») равен 4. В программировании часто предполага- ется, что логарифм вычисляется по основанию 2, поэтому мы используем O(log n) вместо O(log 2 n). Поиск на полке книги, если они упорядочены по алфавиту, является операцией с логарифмическим временем. Сначала вы проверяете книгу в середине полки. Если это та книга, которую вы искали, поиск завершен. В противном случае можно 272 Глава 13.Измерение быстродействия и анализ сложности алгоритмов определить, находится ли искомая книга до или после книги в середине. При этом количество книг, среди которых вы ищете нужную, фактически сокращается вдвое. Этот процесс можно повторить и проверить книгу в середине той половины, где она может находиться. Этот алгоритм называется алгоритмом бинарного поиска; пример его применения рассмотрен в разделе «Примеры анализа “О-большое”» позднее в этой главе, с. 280. Количество разбиений набора из n книг надвое равно log 2 n. На полке с 16 книгами для нахождения нужного издания потребуется не более 4 итераций. Так как каждая сокращает количество книг вдвое, удвоение количества книг добавит в поиск всего один дополнительный шаг. Даже если на упорядоченной полке стоят 4,2 миллиарда книг, для нахождения нужного экземпляра потребуется всего 32 итерации. Алгоритмы log n обычно включают принцип «разделяй и властвуй», который вы- бирает половину входных данных размера n, потом половину от этой половины и т. д. Операции log n хорошо масштабируются: рабочая нагрузка n возрастает вдвое, тогда как время выполнения увеличивается всего на один шаг. O(n), линейное время Чтение всех книг на полке является операцией с линейным временем. Если книги приблизительно одинакового объема, то при удвоении количества книг на полке для чтения понадобится приблизительно вдвое больше времени. Время выполнения растет пропорционально количеству книг n. O(n log n), время N-Log-N Сортировка набора книг в алфавитном порядке является операцией со временем n-log-n. Этот порядок является произведением O(n) и O(log n). Можно рассматри- вать задачу O(n log n) как задачу O(log n), которую необходимо выполнить n раз. Я попробую неформально объяснить почему. Начните со стопки книг, которую необходимо расставить по алфавиту, и пустой книжной полки. Выполните последовательность действий алгоритма бинарного поиска, описанную в подразделе «O(log n), логарифмическое время», с. 271, чтобы определить место одной книги на полке. Как вы уже знаете, эта операция имеет порядок O(log n). Если есть n книг и упорядочение каждой книги требует log n итераций, упорядочение всего набора книг займет n × log n, или n log n итераций. При удвоении количества книг количество шагов увеличится чуть более чем вдвое, так что алгоритмы n log n неплохо масштабируются. Как выясняется, все эффективные обобщенные алгоритмы сортировки имеют порядок O(n log n): сортировка слиянием, быстрая сортировка, пирамидальная Порядки нотации «О-большое» 273 сортировка и Timsort (алгоритм Timsort, изобретенный Тимом Петерсом (Tim Peters), используется методом Python sort() ). O(n 2 ), полиномиальное время Проверка наличия одинаковых книг на неупорядоченной книжной полке является операцией с полиномиальным временем. Если на полке 100 книг, можно начать с первой и сравнить ее с 99 остальными книгами, чтобы узнать, найдется ли такая же. Затем вы берете вторую книгу и сравниваете ее с 99 остальными. Поиск дубли- ката одного издания выполняется на 99 шагов (округлим до 100, то есть n в нашем примере). Это необходимо сделать 100 раз, по одному для каждого экземпляра. Таким образом, количество шагов для выявления всех дубликатов составит прибли- зительно n × n, или n 2 . (Приближение n 2 верно даже в том случае, если действовать умнее и не повторять уже выполненные сравнения.) Время выполнения возрастает в квадратичной зависимости от количества книг. Проверка 100 книг на наличие дубликатов выполняется за 100 × 100, или 10 000 ша- гов. Но при удвоении числа книг потребуется 200 × 200, или 40 000 итераций: объем работы увеличивается в четыре раза. По собственному опыту программирования я обнаружил, что анализ нотации «О-большое» чаще всего используется для того, чтобы избежать случайного применения алгоритма O(n 2 ) там, где действует алгоритм O(n log n) или O(n). Порядок O(n 2 ) обычно становится переломной точкой для существенного за- медления алгоритмов. Когда вы осознаете, что ваш код выполняется со временем O(n 2 ) и выше, стоит сделать паузу. Возможно, есть другой алгоритм, который позволит решить проблему быстрее. В таких ситуациях вам безусловно при- годится учебный курс структур данных и алгоритмов — университетский или онлайновый. Время O(n 2 ) также называют квадратичным. Кроме того, известны алгоритмы с временем O(n 3 ), или кубическим временем, которое медленнее O(n 2 ); алгоритмы с временем O(n 4 ), или биквадратным временем, которое медленнее O(n 3 ), и другие варианты полиномиальной сложности. O(2 n ), экспоненциальное время Фотографирование всех возможных комбинаций книг на полке — операция с экс- поненциальным временем. Логика такова: каждая книга на полке может либо присутствовать на фотографии, либо отсутствовать. На рис. 13.1 изображены все возможные комбинации для n = 1, 2 или 3. Для n=1 возможны всего две фотографии: с книгой и без нее. Если n=2, количество фотографий увеличивается до четырех: обе книги на полке, обе книги не на полке, только первая книга на полке или только 274 Глава 13.Измерение быстродействия и анализ сложности алгоритмов вторая книга на полке. При добавлении третьей книги объем необходимой работы снова удваивается: необходимо обработать каждое подмножество двух книг, ко- торое включает третью книгу (четыре фотографии), и каждое подмножество двух книг, которое не включает третью книгу (еще четыре фотографии — итого 2 3 , или 8 фотографий.) Каждая новая книга удваивает объем работы. Для n книг количество фотографий (то есть объем работы, которую необходимо выполнить) составляет 2 n n = 3 книги 8 комбинаций n = 1 книга 2 комбинации n = 2 книги 4 комбинации Рис. 13.1. Все комбинации книг на полке для одной, двух и трех книг Время выполнения экспоненциальных задач растет очень быстро. Для 6 книг по- требуется 2 6 , или 32 фотографии, но для 32 книг количество фотографий достигает 2 32 , то есть более 4,2 миллиарда фотографий. Алгоритмы O(2 n ), O(3 n ), O(4 n ) и т. д. имеют экспоненциальную сложность. O(n!), факториальное время Фотографирование книг на полке во всех возможных последовательностях — опе- рация с факториальным временем. Все возможные варианты упорядочения n книг называются перестановками. Всего существуют n! (n факториал) перестановок. Факториал числа равен произведению всех положительных целых чисел вплоть до этого числа. Например, факториал 3 равен 3 × 2 × 1, то есть 6. На рис. 13.2 пред- ставлены все возможные перестановки трех книг. Порядки нотации «О-большое» 275 Рис. 13.2. Все 3! (то есть 6) перестановки трех книг на полке Чтобы получить этот результат самостоятельно, подумайте, как бы вы сгенерирова- ли все перестановки n книг. Первую книгу можно выбрать n возможными способа- ми; вторую книгу — n – 1 разными способами (все книги, кроме выбранной в первую позицию); для третьей книги остаются n – 2 возможных варианта, и т. д. Для 6 книг вычисление 6! дает 6 × 5 × 4 × 3 × 2 × 1, или 720 фотографий. При добавлении всего одной книги потребуется 7!, или 5040 фотографий. Даже для небольших значе- ний n часто оказывается, что алгоритмы с факториальным временем невозможно завершить за разумное время. Если вы возьмете 20 книг, будете переставлять их и фотографировать каждую секунду, для перебора всех возможных перестановок потребуется время, превышающее срок существования Вселенной. Среди задач со временем O(n!) хорошо известна задача о коммивояжере. Комми- вояжер должен посетить n городов; он хочет вычислить суммарное расстояние для всех n! возможных вариантов их посещения. По результатам вычислений он рассчитывает определить вариант с кратчайшим расстоянием. При большом количестве городов завершить перебор за разумное время не удастся. К счастью, оптимизированные алгоритмы способны найти короткий (но не обязательно крат- чайший!) маршрут намного быстрее O(n!). «О-большое» как оценка худшего сценария «О-большое» оценивает худший сценарий для любой задачи. Например, чтобы найти конкретную книгу на неупорядоченной книжной полке, вы начинаете с одного конца и просматриваете книги, пока не найдете нужную. Возможно, вам повезет и первая же книга окажется той, которую вы ищете. Но возможна и обратная ситуация: вам не повезет и книга окажется последней или ее вообще не будет на полке. Таким образом, при лучшем сценарии на полке могут быть миллиарды книг — но это неважно, потому что вы немедленно находите искомую книгу. Но при анализе алгоритмов от такого оптимизма нет никакого прока. Нотация «О-большое» описывает, что происходит, если вам не повезет: на полке стоят n книг и вам придется проверить их все. В таком случае время выполнения возрастает пропорционально количеству книг. Некоторые программисты также используют нотацию «Омега-большое», описы- вающую лучший сценарий для алгоритма. Например, алгоритм Ω(n) в лучшем случае работает с линейной эффективностью. В худшем случае он может работать 276 Глава 13.Измерение быстродействия и анализ сложности алгоритмов медленнее. Некоторые алгоритмы сталкиваются с особенно удачными случаями, в которых никакая работа вообще не требуется — например, поиск маршрута, когда вы уже находитесь в конечной точке. Нотация «Тэта-большое» описывает алгоритмы с одинаковыми порядками в луч- шем и худшем случае. Например, Θ(n) описывает алгоритм с линейной эффектив- ностью в лучшем и худшем случае — то есть алгоритм O(n) и Ω(n). Эти обозначения не используются в программировании настолько часто, как нотация «О-большое», но вам следует знать об их существовании. Иногда приходится слышать о быстродействии «О-большое для среднего случая», когда они имеют в виду «Тэта-большое», или «О-большое для лучшего случая», под- разумевая «Омега-большое». Такие высказывания следует считать оксюмороном; «О-большое» относится конкретно к худшему времени выполнения алгоритма. Но несмотря на техническую неточность, вы все равно сможете понять их смысл. ВСЯ НЕОБХОДИМАЯ МАТЕМАТИКА ДЛЯ НОТАЦИИ «О-БОЛЬШОЕ» Если вы подзабыли алгебру, я приведу более чем достаточные математические обоснования для анализа «О-большое». Умножение. Многократное сложение: 2 × 4 = 8, так как 2 + 2 + 2 + 2 = 8. С переменными n + n + n равно 3 × n. Умножение. В алгебраической записи знак × часто опускается, так что 2 × n записывается в виде 2n. С числами 2 × 3 записывается в виде 2(3) или просто 6. Свойство мультипликативного тождества. При умножении числа на 1 будет получено то же число: 5 × 1 = 5, 42 × 1 = 42. В более общем виде n × 1 = n. Дистрибутивность умножения. 2 × (3 + 4) = (2 × 3) + (2 × 4). Обе части запи- си равны 14. В более общем виде a(b + c) = ab + ac. Возведение в степень. Многократное умножение: 2 4 = 16 (читается «2 в чет- вертой степени равно 16»), так как 2 × 2 × 2 × 2 = 16. Число 2 называется основанием, а 4 — показателем степени. С переменными n × n × n × n равно n 4 . В Python для возведения в степень используется оператор **: 2 ** 4 дает результат 16. При возведении в степень 1 результатом является основание степени: 2 1 = 2, а 9999 1 = 9999. В более общем виде n 1 = n. Результат возведения в степень 0 всегда равен 1: 2 0 = 1, и 9999 0 = 1. В более общем виде n 0 = 1. Определение порядка сложности нотации «О-большое» вашего кода 277 Коэффициенты. Множители: в выражении 3n 2 + 4n + 5 коэффициенты равны 3, 4 и 5. 5 тоже является коэффициентом, потому что 5 можно переписать в виде 5(1), а затем записать в виде 5n 0 Логарифм. Операция, обратная возведению в степень. 2 4 = 16, а следо- вательно, log 2 (16) = 4 (читается «логарифм 16 по основанию 2 равен 4»). В Python для вычисления логарифма используется функция math.log(): math.log(16, 2) дает результат 4.0. Вычисление «О-большое» часто требует упрощения формул за счет объеди- нения членов, то есть произведений чисел и переменных: в выражении 3n 2 + + 4n + 5 членами являются 3n 2 , 4n и 5. Подобные члены содержат одинаковые переменные, возведенные в одну степень. В выражении 3n 2 + 4n + 6n + 5 чле- ны 4n и 6n являются подобными. Выражение можно упростить и переписать в виде 3n 2 + 10n + 5. Следует помнить, что поскольку n × 1 = n, выражение вида 3n 2 + 5n + 4 можно рассматривать в виде 3n 2 + 5n + 4(1). Члены этого выражения соответствуют по- рядкам «О-большое» O(n 2 ), O(n) и O(1). Мы еще вернемся к этому факту, когда займемся исключением коэффициентов в вычислениях нотации «О-большое». Эта сводка пригодится нам позднее, когда вы научитесь вычислять порядок сложности нотации «О-большое» для фрагментов кода. Но скорее всего, по- сле раздела «Моментальный анализ сложности» этой главы она вам уже не понадобится. «О-большое» — простая концепция, которая может принести пользу даже без четкого следования математическим правилам. Определение порядка сложности нотации «О-большое» вашего кода Чтобы определить порядок сложности нотации «О-большое» для фрагмента кода, необходимо решить четыре задачи: определить n, подсчитать шаги в коде, исключить нижние порядки и исключить коэффициенты. Для примера найдем сложность «О-большое» для следующей функции rea- dingList() : def readingList(books): print('Here are the books I will read:') numberOfBooks = 0 for book in books: print(book) numberOfBooks += 1 print(numberOfBooks, 'books total.') 278 Глава 13.Измерение быстродействия и анализ сложности алгоритмов Напомню, что n представляет размер входных данных, с которыми работает код. В функциях n почти всегда определяется параметром. У функции readingList() всего один параметр books , и размер books станет хорошим кандидатом для n: чем больше размер books , тем дольше будет выполняться функция. Затем подсчитаем шаги выполнения этого кода. Вопрос о том, что считать шагом, не имеет однозначного ответа, но для начала неплохо ориентироваться на строку кода. Количество шагов в цикле равно количеству итераций, умноженному на ко- личество строк в коде цикла. Чтобы понять, о чем я говорю, приведу подсчеты для кода функции readingList() : def readingList(books): print('Here are the books I will read:') # 1 шаг numberOfBooks = 0 # 1 шаг for book in books: # n * шагов в цикле print(book) # 1 шаг numberOfBooks += 1 # 1 шаг print(numberOfBooks, 'books total.') # 1 шаг Каждая строка кода будет рассматриваться как один шаг — кроме цикла for . Эта строка выполняется один раз для каждого элемента books , а поскольку размер books равен n, можно сказать, что он выполняется за n шагов. Мало того, он выполняет все шаги внутри цикла n раз. Так как цикл содержит два шага, общее количество составляет 2 × n шагов. Шаги можно описать так: def readingList(books): print('Here are the books I will read:') # 1 шаг numberOfBooks = 0 # 1 шаг for book in books: # n * 2 шага print(book) # (уже подсчитано) numberOfBooks += 1 # (уже подсчитано) print(numberOfBooks, 'books total.') # 1 шаг Теперь при вычислении общего количества шагов мы получаем 1 + 1 + (n × 2) + 1. Это выражение можно переписать в упрощенном виде 2n + 3. Нотация «О-большое» не предназначена для описания конкретных значений; это общий индикатор. По этой причине из подсчетов исключаются нижние порядки. Выражение 2n + 3 состоит из двух порядков, линейного (2n) и постоянного (3). Если оставить только больший из этих порядков, остается 2n. Затем из порядка исключаются коэффициенты. В 2n коэффициентом является 2. После исключения остается n. В результате мы получаем итоговую метрику нота- ции «О-большое» для функции readingList() : O(n), то есть линейная сложность. Если задуматься, этот порядок выглядит логично. Функция состоит из нескольких шагов, но в общем случае при увеличении списка books в 10 раз время выполнения Определение порядка сложности нотации «О-большое» вашего кода 279 также увеличится десятикратно. При увеличении размера books с 10 до 100 алго- ритм переходит от значения 1 + 1 + (2 × 10) + 1, или 23 шага, к 1 + 1 + (2 × 100) + 1, или 203 шага. Число 203 равно приблизительно 10 × 23, так что время выполнения возрастает пропорционально росту n. |