Анализ алгоритмов

Analyzing Algorithms

В этой главе мы узнаем In this chapter, you will learn:

• как пользоваться обозначением О большое для определения класса вычислительной сложности алгоритма по времени или по памяти; How to use the Big O notation to classify the performance of algorithms (in time or storage)

• какие бывают основные классы сложности, например: Several performance classes, including:

  • O(1) — константный ,

  • O(log N) — логарифмический,

  • O(N) — линейный,

  • O(N log N) — N-логарифмический¹,

  • O(N²) — квадратичный;

• как применять асимптотический анализ по N для оценки времени работы (или потребляемой памяти) алгоритма на наборе данных размера N; How asymptotic analysis estimates in terms of N the time (or storage space) required by an algorithm to process a problem instance of size N.

• как работать с массивами данных, элементы которых упорядочены по возрастанию; How to work with arrays whose values appear in ascending, sorted order.

• как устроен алгоритм двоичного поиска элемента в сортированном списке. The Binary Array Search algorithm to locate values in a sorted array.

переведённая сноска 1 Pronounced using three syllables, like en-log-en.

В этой главе вводятся обозначения и терминология из теории сложности алгоритмов, которая на практике используется для оценки их быстродействия и объёма потребляемой ими памяти. Если некоторая программа работает без нареканий — вполне быстро с любыми данными, что попадаются на практике — скорее всего, её не стоит улучшать. Наша книга посвящена тому, с чего начинать, когда требуется улучшить быстродействие — алгоритмам и структурам данных. И тогда возникают вот такие вопросы: This chapter introduces the terminology and notation used by theoreticians and practitioners alike in modeling the performance of algorithms in terms of computa‐ tional performance and resource usage. When evaluating the runtime performance of your software program, you might be perfectly satisfied, in which case you can con‐ tinue to use the application as is. But if you want to improve runtime performance, this book shows you where to start—with the program’s data structures and algo‐ rithms. You are faced with some specific questions:

Точно ли нынешнее решение — самое эффективное? Am I solving a specific problem in the most efficient way?

• Вполне могут существовать алгоритмы, которые решают задачу значительно быстрее. There may be other algorithms that would significantly improve performance.

Насколько эффективна реализация алгоритма? Am I implementing an algorithm in the most efficient way?

• В тексте программы могут оказаться конструкции, требующие неожиданно много ресурсов. There can be hidden performance costs that can be eliminated.

Может, купить компьютер помощнее? Should I just buy a faster computer?

• Одна и та же программа на разных машинах работает с разной скоростью. Мы посмотрим, какими способами специалисты по компьютерам учитывают обновление аппаратного обеспечения при анализе. The exact same program will have different runtime performance based on the computer on which it runs. In this chapter, I explain how computer scientists have developed analysis techniques that account for regular hardware improvements.

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

I start by showing how to model the runtime performance of a program on ever- increasing problem instance sizes. The runtime performance of an algorithm on small problem instance sizes can be hard to measure accurately because it could be sensitive to the actual values in the problem instance or to the resolution of the com‐ puter timers. Once your program processes a sufficiently large problem instance, you can develop models to classify its runtime behavior using empirical models.

Как оценить сложность с помощью эмпирической модели

Using Empirical Models to Predict Performance

Лучше всего начать сразу с примера, в котором теоретический анализ оказывается в исследовании конкретных программных систем очень даже практичным. Предположим, вы делаете приложение — часть большого задания, которое еженощно обрабатывает большой набор данных. Задание запускается в полночь и должно отработать до шести утра. Ночной набор данных состоит из нескольких миллионов значений — и ожидается, что лет за пять его объём удвоится². I’d like to start with an example that shows how theoretical analysis is decidedly prac‐ tical in real software systems. Imagine you are in charge of designing an application as part of a nightly batch job to process a large data set each night; the task is launched at midnight and must complete before 6:00 a.m. The data set contains sev‐ eral million values and is expected to double in size over the next five years.

И вот вы уже написали работающий прототип, но тестируете его на небольших наборах данных — по 100, 1000 и 10000 элементов. В таблице 2-1 зафиксировано время работы прототипа на этих данных. You have built a working prototype but have only tested it on multiple small data sets, with 100, 1,000, and 10,000 values each. Table 2-1 presents the runtime performance of your prototype on these data sets.

• Таблица 2-1. Время работы прототипа Table 2-1. Prototype runtime performance

Можно ли по этим предварительным результатам прогнозировать время работы прототипа на больших наборах данных, например, на 100 000 или миллионе значений? Попробуем построить математическую модель на основании только этих результатов и найдём некоторую функцию T(N), которая будет предсказывать время работы на данных заданного объёма. Достоверная модель не только вычислит T(N) достаточно близко к трём значениям из таблицы 2-1, но ещё и предскажет время работы на больших наборах, представленное в таблице 2-2 (известные нам результаты указаны в ней в квадратных скобках). Can these preliminary results predict the performance of your prototype on larger problem instances, such as 100,000 or even 1,000,000? Let’s build mathematical mod‐ els from this data alone to define a function T(N) that predicts the runtime perfor‐ mance for a given problem instance size. An accurate model will compute a T(N) that is close to the three values in Table 2-1, as well as predict higher values of N, as shown in Table 2-2 (which repeats these three time results in brackets).

Возможно, вы пользовались инструментами, которые умеют находить линейную регрессию заданного набора данных, например, Maple (https://maplesoft.com) или Microsoft Excel (https://microsoft.com/excel). Регрессионные модели можно построить и с помощью SciPy — библиотеки Python для математических, общенаучных и инженерных расчётов. В примере 2-1 показано, как с помощью numpy подобрать константы a и b в линейном приближении TL(N) = a * N + b . Функция curve_fit() возвращает пару коэффициентов (a, b) линейного приближения на основании экспериментальных данных, которые передаются ей в списках xs и ys³. You may have used a software tool, such as Maple (https://maplesoft.com) or Micro‐ soft Excel (https://microsoft.com/excel), to compute a trendline (also called a line of best fit) for sample data. The popular SciPy library for mathematics, science, and engineering can develop these trendline models. Listing 2-1 uses scipy to try to find a linear model, TL(N) = a × N + b, where a and b are constants. curve_fit() will return the (a, b) coefficients to use with the linear model based on the available empirical data encoded in lists xs and ys.

   1 import numpy as np
   2 from scipy.optimize import curve_fit
   3 
   4 def linear_model(v, a, b):
   5   return a*v + b
   6 
   7 # Экспериментальные данные
   8 xs = [100, 1000, 10000]
   9 ys = [0.063, 0.565, 5.946]
  10 
  11 # Первое возвращаемое значение — массив из двух коэффициентов
  12 (a, b), _ = curve_fit(linear_model, xs, ys)
  13 print(f'Linear = {a}*N + {b}')

• Пример 2-1. Построение приближения на неполных данных Listing 2-1. Calculate models based on partial data

Полученная математическая модель выражается формулой TL(N) = 0.000596·N - 0.012833. Из таблицы 2-2 понятно, что приближение это не слишком достоверно: чем больше размер входного набора, тем сильнее прогноз времени работы прототипа отстаёт от результатов эксперимента. Можно попробовать повысить степень N до второй и построить квадратичное приближение⁴: The resulting model is the formula TL(N) = 0.000596 × N – 0.012833. As you can see from Table 2-2, this model is inaccurate because as the problem size increases, it sig‐ nificantly underestimates the actual runtime performance of the prototype. Another possible model is a quadratic polynomial, where N is raised to the power of 2:

   1     def quadratic_model(v, a, b):
   2       return a*v*v + b*v;

Задача анализа — подобрать такие параметры a и b функции quadratic_model(), чтобы полученная формула TQ(N) = a·N² + b·N соответствовала имеющимся данным. Если исследовать её по аналогии с примером 2-1, получится формула TQ(N) = 0.000000003206·N² + 0.000563·N. Таблица 2-2 показывает, что эта модель тоже недостоверна: её прогноз времени работы на больших наборах тем сильнее опережает экспериментальные результаты, чем больше данных в наборе. With quadratic_model, the goal is to find TQ(N) = a × N2 + b × N, where a and b are constants. Using the approach in Listing 2-1, the formula is TQ(N) = 0.000000003206 × N2 + 0.000563 × N. Table 2-2 shows that as the problem size increases, this model significantly overestimates the actual runtime performance, so it is also not accurate.

Большинство найденных нами коэффициентов, например, 0.000000003206, т. е. 3.206 · 10⁻⁹, — довольно малые числа. Это происходит оттого, что наши алгоритмы работают на больших наборах данных, где N = 1 000 000 и даже больше. Тот же миллион, возведённый в квадрат — это 1 000 000² = 10¹², так что стоит ожидать, что нам встретятся и очень большие, и очень маленькие числа.

Последний столбец таблицы 2-2 — время работы, оцененное третьей математической моделью, TN(N) = a·log₂ N: в ней один коэффициент — a, а в формуле присутствует двоичный логарифм. Полученное приближение — TN(N) = 0.0000448·log₂ N. Для N = 10 000 000 погрешность приближённого значения находится в пределах 5% от экспериментального. The final column in Table 2-2 contains the predicted result using a third mathemati‐ cal model, TN(N) = a × N × log(N), which uses the logarithm function (in base 2) and in which a is a constant. The result is TN(N) = 0.0000448 × N × log(N). For N = 10,000,000, the estimate computed by TN(N) is within 5% of the actual value.

• Таблица 2-2. Сравнение результатов различных математических моделей с фактическим временем работы Table 2-2. Comparing different mathematical models against actual performance

Линейное приближение, TL, сильно преуменьшает время работы, а квадратичное, TQ — преувеличивает. Расчёт времени для N = 10 000 000 у TL равен 5957 секунд (это минут сто), а у TQ — целых 326300 (почти 91 час). У TN предсказывать быстродействие получается куда лучше: ожидаемое время по TN — 10421 секунда (примерно 2.9 часа), а фактическое — 9879 секунд (2.75 часа). The linear model, TL, underestimates the total time, while the quadratic model, TQ, overestimates it. For N = 10,000,000, TL declares it will take 5,957 seconds (about 100 minutes), but TQ declares it will take 326,300 seconds (about 91 hours). TN does a bet‐ ter job in predicting the performance, estimating 10,421 seconds (about 2.9 hours) against the actual performance of 9,879 seconds (2.75 hours).

Прототип, слава богу, за ночь всё обработал. Но всё же имеет смысл просмотреть его исходный текст на предмет задействованных в нём алгоритмов и структур данных. Только тогда можно будет утверждать с уверенностью, что он будет работать примерно столько же на любых данных того же размера. The prototype completes its processing overnight—that’s a relief!—but you must review the code for your prototype to see the algorithms and data structures it employs, so you can guarantee this result regardless of the problem instance being solved.

Отчего формула a·N·log₂ N так хорошо предсказывает поведение программы? Это наверняка зависит от того, какие алгоритмы лежат в основании самой программы. Оценка сложности алгоритмов часто выдаёт одно из наших трёх приближений — линейное, квадратичное или N-логарифмическое. Следующий пример напомнит нам об одном удивительном открытии шестидесятилетней давности⁵. Why does the formula a × N × log(N) model the behavior so well? It has to do with the fundamental algorithms used within your prototype application. These three kinds of models—linear, quadratic, and N log N—appear regularly when analyzing algorithms. Let’s try one more example to demonstrate a surprising result discovered about fifty years ago.2 2 A fast multiplication algorithm was discovered in 1960 by a 23-year old student at Moscow State University named Anatoly Karatsuba. Python uses this algorithm when multiplying very large integers.

Умножать быстрее, чем в столбик?

Multiplication Can Be Faster

В примере 2-2 показаны два умножения N-значных чисел в столбик, алгоритм которого большинство из нас знает со времён начальной школы. Даже не вдаваясь в подробности алгоритма, мы можем заметить, что в процессе умножения создаётся N промежуточных произведений, которые записываются ниже исходных чисел, а ответ представляет собой сумму этих (слегка преобразованных) произведений. Consider two examples, shown in Listing 2-2, for multiplying two N-digit integers using an algorithm most of us learned in grade school. While I do not precisely define this algorithm, you see that it creates N products, listed below the original numbers, which are totaled to compute the final answer.

   456                    123456
 x 712                  x 712835
   ---                    ------
   912                    617280
  456                    370368
3192                    987648
------                 246912
324672                123456
                     864192
                     -----------
                     88003757760

• Пример 2-2. Школьный алгоритм умножения N-значных чисел Listing 2-2. Using grade-school algorithm to multiply two N-digit integers

Чтобы умножить два трёхзначных числа друг на друга, надо перемножить девять пар цифр. Два шестизначных числа потребуют уже тридцать шесть умножений отдельных цифр. Умножая таким способом два N-значных числа, мы выполняем N² умножений цифр. Можно ещё заметить, что от увеличения количества цифр в целочисленных множимом и множителе вдвое количество действий «умножение цифры на цифру» растёт вчетверо. Другие операции (например, сложение) можно даже не считать — умножение важнее. When multiplying two 3-digit integers, you need 9 single-digit multiplications. For 6- digit integers, you need 36 single-digit multiplications. Using this algorithm with two N-digit integers requires N2 single-digit multiplications. Another observation is that when you double the number of digits in the integers being multiplied, you need four times as many single-digit multiplications. I’m not even counting all the other work to do (like additions) because single-digit multiplication is the key operation.

Центральный процессор ЭВМ умеет быстро умножать целые числа только фиксированного размера — 32 или 64-разрядные, но с числами большей длины самостоятельно не справляется. Если целое число в Python оказывается слишком большим, оно преобразуется в специальную структуру PyLong, которая увеличивается по мере роста числа. Вот на ней и можно исследовать быстродействие умножения произвольных N-значных целых. В таблице 2-3 приведены результаты вычислений четырёх эмпирических моделей производительности, которые построены на основании первых пяти экспериментальных данных (выделены квадратными скобками). A computer’s CPU provides efficient operations to multiply fixed-size 32-bit or 64-bit integers, but it has no ability to deal with larger integers. Python automatically upgrades large integer values to a Bignum structure, which allows integers to grow to any size necessary. This means you can measure the runtime performance when mul‐ tiplying two N-digit numbers. Table 2-3 derives three models based on the first five rows of timing results of multiplying two N-digit integers (shown in brackets).

• Таблица 2-3. Умножение N-значных чисел Table 2-3. Multiplying two N-digit integers

Здесь TL — линейное приближение, а TQ — квадратичное. Karatsuba — это приближение с нестандартной степенью, a·N¹·⁵⁸⁵, а TKN — более соответствующая экспериментальным данным формула, TKN(N) = a·N¹·⁵⁸⁵ + b·N, с аккуратно подобранными коэффициентами a и b.⁶ TL значительно недооценивает время работы умножения. А вот TQ — значительно переоценивает, хотя можно было ожидать, что квадратичное приближение окажется достаточно достоверным: количество действий при умножении столбиком растёт квадратично, о том же говорит и увеличение времени работы вчетверо при росте длины чисел вдвое. Но две других математических модели оказались намного достовернее для расчёта времени, за которое в Python умножаются N-значные целые, — потому что для этого используется более эффективный алгоритм Карацубы умножения длинных целых⁷. TL is a linear model, while TQ is a quadratic model. Karatsuba is the unusual formula a × N1.585, and the improved model TKN(N) = a × N1.585 + b × N, where a and b are constants.3 TL significantly underestimates the time. TQ significantly overestimates the time, which is surprising since earlier intuition suggests that when N doubles, the time to perform should increase fourfold, an essential characteristic of quadratic models. These other models more accurately predict the performance of multiplying N-digit integers in Python, which uses an advanced, more efficient Karatsuba multi‐ plication algorithm for large integers.

Эмпирический подход, иллюстрируемый таблицами 2-2 и 2-3, неплох для начала, но недостаточен: мы изучаем не сам алгоритм напрямую, даже не исходный текст программы, а только результаты работы. Когда нашей книге нам будут встречаться конкретные реализации алгоритмов, мы будем изучать структуру исходных текстов и оценивать быстродействие, выводя подходящую формулу на основании этой структуры. The approach used to generate Table 2-2 and Table 2-3 is a good start, but it is limited since it is indirect, based only on runtime performance and not by reviewing the code. Throughout this book, I will describe the implementations of the algorithms, and based on the structure of the code, I can identify the appropriate formula to model the performance of an algorithm.

Классы вычислительной сложности

Performance Classes

Иногда понять, какой из двух алгоритмов эффективнее справляется с одной и той же задачей, довольно просто: достаточно оценить их вычислительную сложность с помощью математических моделей. Обычно говорят «сложность O(N²) или «в худшем случае сложность N log N». Чтобы начать в этом разбираться, давайте посмотрим на иллюстрацию 2-1. Тем, кто прочёл книжку по теории сложности или изучал материалы в Сети по анализу алгоритмов, картинка покажется знакомой. When different algorithms solve the exact same problem, it is sometimes possible to identify which one will be the most efficient simply by classifying its performance using mathematical models. Often algorithms are described using phrases like “Com‐ plexity is O(N2)” or “Worst-case performance is O(N log N).” To explain this termi‐ nology, I want to start with the image in Figure 2-1, which might be a familiar one if you have read a book, or an online resource, that discusses algorithm analysis.

Наша задача — построить математическую модель, которая оценивает время работы в наихудшем случае для набора данных размера N. Математики это называют верхней границей; проще говоря, алгоритм никогда не проработает дольше приведённой оценки. Соответственно, нижняя граница оценки относится к минимальному времени работы и звучит как «алгоритм всегда проработает как минимум столько-то». The goal is to find a model that predicts the worst runtime performance for a given problem instance, N. In mathematics, this is known as an upper bound—think of the phrase “the algorithm will never work harder than this.” A corresponding concept, the lower bound, represents the minimum runtime performance—in other words, “the algorithm must always work at least this much.”

Поясним понятия верхней и нижней границы на примере автомобильного спидометра. Задача спидометра — вычислять и показывать приблизительное значение текущей скорости автомобиля. Скорость, которую показывает спидометр, должна быть не ниже текущей, чтобы водитель мог соблюдать правила движения. Это и есть нижняя граница. В большую сторону показания скорости не должны превышать 110% плюс 4 км/ч от текущей.⁸ В математике это соответствует понятию верхней границы. To explain the concepts of lower and upper bounds, consider how a car’s speedome‐ ter is a model that computes an indicated speed as an approximation of the car’s true speed. The indicated speed must never be less than the true speed so the driver can abide by speed limits. This represents the mathematical concept of a lower bound. On the high end, the indicated speed is allowed to be up to 110% of the true speed plus 4 kilometers per hour.4 This represents the mathematical concept of an upper bound.

Текущая скорость автомобиля не может быть больше показаний спидометра. Стало быть, мы можем принять её за верхнюю границу и относительно несложно высчитать минимально возможную скорость, которая будет совпадать с соответствующей нижней границей. The true speed for the car must always be larger than the lower bound and smaller than the upper bound.

3 The exponent, 1.585, is the approximate value of log(3) in base 2, which is 1.58496250072116. 4 This is a European Union requirement; in the United States, it is sufficient for the speedometer to be accurate to within plus or minus 5 miles per hour.

На иллюстрации 2-1 изображены три графика, которые представляют три наших приближения «длинного умножения» в Python — TL, TQ и TKN; экспериментальные данные обозначены там же чёрными квадратиками. TQ(N) — очевидная верхняя граница эксперимента (ибо TQ(N) всегда меньше экспериментального значения на всех N), но по самой иллюстрации видно, что эта граница очень неточная. In Figure 2-1, the three curves—TL, TQ, and TKN—represent the model predictions, while black squares represent the individual actual performance when multiplying two N-digit integers. While TQ(N) is an upper bound on the actual performance (since TQ(N) > Time for all values of N), it is highly inaccurate, as you can see from Figure 2-1.

Иллюстрация 2-1. Сравнение математических моделей с результатами измерений производительности

Если повнимательнее посмотреть на таблицу 2-3, можно заметить, что начиная с порогового значения объёма входных данных N=8192 приближение TKN(N) тоже всегда больше эмпирических данных для остальных N — но при этом гораздо к ним ближе. Обычно это признак того, что функция стабилизировалась, и будет вести себя так впредь для «достаточно больших» N, но для каких именно — зависит от самого алгоритма и его конкретной реализации. If you go back and review Table 2-3, observe that for all N values greater than or equal to the threshold problem instance size of 8,192, TKN(N) is greater than the actual performance reported for N, while remaining much closer to the actual values. This evidence is a clear indication that often the real behavior will stabilize once N is “large enough,” which will depend on each algorithm and the way it is implemented.

Очевидно также, что линейное приближение TL(N) — это нижняя граница времени работы, потому что TL(N) меньше эмпирических данных для любого N. Впрочем, при увеличении N эта формула всё сильнее отстаёт от экспериментальных значений, так что в качестве математической модели становится вполне бесполезной. Более точной нижней границей оказывается формула, названная в таблице 2-3 «Karatsuba»: a · N¹·⁵⁸⁵. It might seem that TL(N) models the lower bound on the actual performance, since TL(N) < Time for all values of N. However, as N increases, it becomes further and fur‐ ther away from the runtime performance, essentially rendering it useless as a model of the algorithm’s runtime performance. The Karatsuba formula a × N1.585, whose val‐ ues appear in Table 2-3, provide a more accurate lower bound.

Оценку производительности можно запускать на разных компьютерах, при этом конкретные числовые характеристики в таблице 2-3 поменяются. Скорость умножения может быть меньше или больше, коэффициенты a и b в TKN(N) могут оказаться другими, сама TKN(N) может стабилизироваться на другом большем или меньшем N. Но степень 1.585 в формулах не поменяется, потому что такова организация алгоритма быстрого умножения Карацубы, которым и определяется быстродействие. Никакой суперкомпьютер⁹ не сможет заставить умножение работать со скоростью линейного приближения TL(N). If you run these programs on different computers, the numeric details shown in Table 2-3 will change—the runtime performance can be slower or faster; the a and b coefficients of TK() will change; the threshold problem instance size above which TK(N) stabilizes could be lower or higher. What would remain unchanged is the expo‐ nent 1.585 in the model, since the structure of the Karatsuba fast multiplication algo‐ rithm determines how it will perform. No supercomputer will somehow make the Karatsuba implementation suddenly behave in a way modeled by the linear TL(N) model.

Настало время заняться асимптотическим анализом — методикой, которая позволит нам при оценке быстродействия алгоритма вообще не обращать внимания на скорость работы конкретных компьютеров. Мощный компьютер может заставить программу работать быстрее, но не может изменить законы асимптотического анализа! We can now tackle asymptotic analysis, an approach that lets us eliminate any knowl‐ edge about the actual computer when evaluating the performance of an algorithm. Powerful computers can make code run faster, but they cannot bend the laws of asymptotic analysis.

Асимптотический анализ

Asymptotic Analysis

Понятие аддитивной постоянной часто встречается в обыденной жизни, например, в нашем недавнем разговоре про спидометры. Когда мы говорим «приеду минут через сорок, плюс-минус пять минут», мы имеем в виду как раз аддитивную постоянную. The concept of an additive constant is common in many real-world scenarios, like the speedometer I just discussed. It’s what we mean when we say, “I’ll be there in 40 minutes, give or take 5 minutes.”

В асимптотическом анализе эта идея развивается, и вводится понятие мультипликативной постоянной алгоритма. Кто слышал о «Законе Мура», уже представляет себе, в чём оно состоит. Ещё в 1965 году Гордон Мур, один из основателей и генеральных директоров корпорации Intel, высказал предположение, что количество элементов в интегральных микросхемах будет удваиваться ежегодно в течение ближайших десяти лет. В 1975-м он его скорректировал: «количество элементов в интегральных микросхемах удваивается каждые два года». Это наблюдение остаётся верным более 40 лет, и пока оно верно, скорость работы компьютеров тоже удваивается примерно за два года. Такая «мультипликативная постоянная в истории вычислительной техники» означает, что одна и та же программа на старом компьютере будет работать в тысячу раз медленнее (а то и хуже), чем на новом.

Asymptotic analysis takes this idea further and introduces the notion of a multiplica‐ tive constant to analyze algorithms. If you’ve heard of Moore’s Law, you will find this concept familiar. Gordon Moore, the CEO and cofounder of Intel corporation, pre‐ dicted in 1965 that the number of components per integrated circuit would double every year for a decade; in 1975 he revised this prediction to doubling every two years. This prediction was valid for over 40 years and explains why the speed of com‐ puters essentially doubles every two years. A multiplicative constant applied to com‐ puting means you can find an older computer where the same program runs one thousand times slower (or even worse) than on a modern computer.

Возьмём два алгоритма, решающих одну и ту же задачу. Изучив их уже известным нам способом, предположим, что алгоритм X требует 5·N действий на наборе данных размера N, а алгоритм Y — 2020*log₂ N действий на том же входном наборе. Какой из них эффективнее — X или Y? Consider two algorithms that solve the same problem. Using the techniques I have already shown, assume that algorithm X requires 5N operations on problems of size N, while algorithm Y requires 2020 × log(N) operations to solve the same problem. Is algorithm X more efficient than Y?

Мы реализовали оба алгоритма и запускаем программы на двух компьютерах — один назовём C_fast, и он в два раза быстрее второго, C_slow. На иллюстрации 2-2 приведено количество действий, затраченных каждым алгоритмом на входных данных объёма N, а также время работы обоих алгоритмов на компьютере C_fast (столбцы обозначены как X_fast и Y_fast) и на компьютере C_slow (столбцы X_slow и Y_slow соответственно). You have two computers on which you execute implementations of these algorithms: computer Cfast is two times faster than Cslow. Figure 2-2 reports the number of opera‐ tions for each algorithm on a problem instance of size N. It also shows performance of X and Y on Cfast (i.e., columns labeled Xfast and Yfast) and the performance of X on Cslow (i.e., column labeled Xslow).

Иллюстрация 2-2. Производительность алгоритмов X и Y на разных компьютерах

На небольших наборах данных одинакового размера алгоритму X требует меньше действий, чем Y, однако начиная с N=8192 Y становится экономнее X, и чем N больше, тем разница сильнее. На иллюстрации 2-3 видна точка пересечения графиков между 4096 и 8192, после которой Y оказывается эффективнее X по количеству выполняемых действий. На двух разных компьютерах идентичные реализации алгоритма X закономерно покажут, что X_fast, запущенный на C_fast, всегда быстрее X_slow, запущенного на C_slow. While initially X requires fewer operations than Y on problem instances of the same size, once N is 8,192 or larger, Y requires far fewer operations, and it’s not even close. The graphs in Figure 2-3 visualize the crossover point between 4,096 and 8,192, when Y begins to outperform X in terms of the number of operations required. When you run the exact same implementation of X on two different computers, you can see that Xfast (running on Cfast) outperforms Xslow (running on Cslow).

Допустим, мы нашли суперкомпьютер C_fastest, который в 500 раз быстрее, чем C_slow. Можно отыскать такой объём входных данных, начиная с которого эффективный алгоритм Y будет работать на C_slow быстрее, чем неэффективный — на C_fastest. Мы тут, конечно, немножко «сравниваем тёплое с мягким» — компьютеры-то разные! — но всё равно, даже в нашем случае точка пересечения возникает между наборами размером в 4 194 304 и 8 388 608. Если алгоритм в конечном счёте более эффективен, работая на даже медленном компьютере, он обгонит неэффективный алгоритм, запущенный на суперкомпьютере — если объём входных данных достаточно велик. If you found a supercomputer, Cfastest, that was 500 times faster than Cslow, you could eventually find a problem instance size for which the efficient algorithm Y, running on Cslow, outperforms the inefficient algorithm X, running on Cfastest. This is an “apples vs. oranges” comparison in a way, because the programs are running on different computers; nonetheless, in this specific case, the crossover occurs on problem instance sizes between 4,194,304 and 8,388,608. Even with a supercomputer, eventu‐ ally the more efficient algorithm will outperform it on a slower computer, once the problem instances are large enough.

Иллюстрация 2-3. Графики для числовых данных иллюстрации 2-2

Сколько ни трать дополнительных вычислительных мощностей на решение задачи, всё равно найдутся такие объёмы данных, начиная с которых более эффективный алгоритм работает быстрее. You can try to throw advanced computing hardware at a problem, but eventually the more efficient algorithm will be faster for large-enough problem instances.

В математике для классификации вычислительной сложности алгоритмов (и в худшем, и в лучшем случаях) используется обозначение «O большое». «O» в данном случае означает «order», т. е. «порядок». Порядок функции — это скорость, с которой она растёт при росте её переменной, N. Например, формула 4·N² + 3·N - 5 — «порядка N²» (или квадратичная), потому что быстрее всего в этом многочлене растёт первое слагаемое, в котором степень N равна 2. Computer scientists use a Big O notation to classify algorithms based on the runtime performance on best case (or worst case) problem instances of size N. The letter O is used because the growth rate of a function is called the “order of a function.” For example, the formula 4N2 + 3N – 5 is an “order 2” function, also called quadratic, since the largest exponent for N is 2.

Для оценки быстродействия алгоритма на наборе данных размера N обычно начинают считать количество выполненных им действий. Предполагается, что каждое действие выполняется за фиксированное время, что и превращает этот подсчёт в оценку предполагаемого времени работы. To estimate the runtime performance for an algorithm on a problem instance of size N, start by counting the number of operations. It’s assumed that each operation takes a fixed amount of time to execute, which turns this count into an estimate for the runtime performance.

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

Подсчёт всех действий

Counting All Operations

Наша задача — оценить время работы алгоритма на произвольном наборе данных размера N. Поскольку такая оценка должна быть достоверной для всех возможных данных, стоит подобрать набор для наихудшего случая, на котором алгоритм работает дольше всего. The goal is to estimate the time for an algorithm to process any problem instance of size N. Because this estimate must be accurate for all problem instances, try to find a worst case problem instance that will force the algorithm to work the most.

Для начала определим функцию K(N) — количество основных действий, выполняемых в наихудшем случае на наборе данных размера N. Затем оценим число выполняемых машинных инструкций той же функцией с коэффициентом: c·K(N). Поскольку в современных языках программирования одно действие может быть транслировано в десятки, а то и тысячи инструкций, предосторожность в виде константы c будет нелишней. Вычислять её необязательно, хотя подобрать опытным путём с учётом производительности конкретного компьютера, как мы это делали раньше, вполне возможно. First, determine K(N), the count of how many times a key operation executes on a worst case problem instance of size N. Next, estimate that the number of machine instructions executed in total would be a multiple of this count, that is c × K(N). This is a safe assumption because modern programming languages can be compiled into tens or hundreds of machine instructions. You don’t even have to compute c, but rather you can empirically determine it, based on the individual performance on a computer, as I have done.

Классификация вычислительной сложности (или потребления памяти) алгоритмов напрямую сопоставляет сложность с некоторой функцией от N. Этой функцией, f(N), описывается класс сложности O(f(N)) (поначалу в терминах легко запутаться). Относя алгоритм к определённому классу, мы составляем формулу в виде функции f от N. Нам уже встречались четыре класса сложности: The notation clearly classifies the trajectory of the performance (or storage) as a func‐ tion of N. Each performance class O(f(N)) is described by some f(N). The terminol‐ ogy can, at first, be confusing. When classifying the algorithm, you will use a formula represented as a function, f, based on N. We have seen four performance classes:

1. O(N) — линейная сложность, где f(n) = N. O(N) is the linear complexity class, where f(N) = N.

2. O(N¹·⁵⁸⁵) — сложность Карацубы, где f(N) = N¹·⁵⁸⁵. O(N1.585) is the Karatsuba complexity class, where f(N) = N1.585.

3. O(N²) — квадратичная сложность, где f(N) = N². O(N2) is the quadratic complexity class, where f(N) = N2.

4. O(N log N) — N-логарифмическая сложность, где f(N) = N log N¹⁰. O(N log N) is the complexity class where f(N) = N × log N.

Для точного анализа надо изучать исходный текст программы и выявлять организацию алгоритма. Сколько раз выполняется действие ct += 1 в примере ниже? To conduct an accurate analysis, you must inspect the source code to see the structure of the algorithm. In the following code example, how many times does the key opera‐ tion ct = ct + 1 execute?

   1        for i in range(100):
   2          for j in range(N):
   3              ct += 1

Внешний цикл, по i, делает 100 проходов, и на каждом из них из них внутренний цикл, по j, делает N проходов. Итого действие ct += 1 выполняется 100 * N раз. При должном выборе константы c время выполнения приведённого фрагмента программы T(N) на наборе данных размера N не будет превышать c * N. Запуская программу на конкретном компьютере можно определить значение соответствующего c. Говоря точнее, в терминах «О большого», сложность этого фрагмента оценивается как O(N). The outer i loop executes 100 times, and for each of these loops, the inner j loop executes N times. In total, ct = ct + 1 executes 100 × N times. The total time T(N) to execute the preceding code on a problem instance of size N is smaller than c × N for some suitably chosen c. If you execute this code on an actual computer, you will be able to determine the exact c. More precisely, using the Big O notation, we can state that the performance of this code is O(N).

Модно запускать эту программу тысячи раз на самых разных компьютерах, можно даже каждый раз получать различные значения коэффициента c — порядок сложности алгоритма не изменится, именно это мы и имели в виду, оценивая сложность как O(N). Если не углубляться в дебри теории, достаточно знать вот что: если мы подобрали некоторую функцию f(N), которая оценивает количество действий, выполняемых нашим алгоритмом, тем самым мы автоматически классифицируем сложность этого алгоритма как O(f(N)). Run this code thousands of times on different computing systems, and each time you would be able to compute a different c; this fact remains true and is the reason we can classify the code performance as O(N). There are theoretical details I sidestep in this discussion, but you only need to know that when you have identified a function, f(N), that represents the count of the operations in your algorithm, you have its algo‐ rithm classification, O(f(N)).

Подсчёт всех байтов

Counting All Bytes

Такой же анализ можно проделать для оценки «сложности по памяти» — объёма памяти, потребляемого алгоритмом на входных наборах размера N. Динамическое выделение дополнительной памяти неизбежно ведёт и к понижению производительности, потому что управление памятью — это тоже алгоритм, со своей сложностью. You can perform a similar analysis to determine the space complexity required for an algorithm on a problem instance of size N. When an algorithm dynamically allocates additional storage space, it invariably increases the runtime performance because of the costs associated with dynamic memory management.

Вот такие конструкции Python требуют совершенно разных объёмов памяти: The following Python statements require a different amount of space:

• range(N) занимает константный, не зависящий от N объём оперативной памяти — потому что объект типа range — это арифметическая прогрессия, любой элемент которой можно вычислить, а не хранить их все в памяти (когда-то, ещё в Python2, range() была просто функцией, возвращавшей список). range(N) uses a fixed amount of space because in Python 3, range is a generator that produces the numbers one at a time, without allocating a whole list (as it did in Python 2).

• list(range(N)) сделает из такой последовательности список с элементами от 0 до N-1. Такому объекту требуется оперативная память в объёме, прямо пропорциональном N. list(range(N)) constructs a list storing N integers from 0 to N – 1. The size of the required memory grows larger in direct proportion to N.

Чётко определить объём той или иной конструкции языка программирования непросто уже потому, что не до конца понятно, в чём его измерять. Допустим, в байтах или битах? Но тогда имеет ли значение, что на некоторых архитектурах целое число занимает 32 бита, а на некоторых — 64? Допустим, в будущем появится компьютер, оперирующий 128-битными целыми¹¹ — значит ли это, что сложность по памяти при работе с целыми числами для них удвоится? Размер объекта в байтах в Python показывает функция sys.getsizeof(объект). Давайте на примере убедимся, что использование вычислимой последовательности range() в Python 3 позволяет ощутимо сэкономить потребление памяти! Для это достаточно запустить интерпретатор python3 и подать ему такие команды: Quantifying the space for a statement is hard because there is no universally agreed- upon unit for space. Should we count the bytes of memory used? The bits? Does it matter if an integer requires 32 bits of storage or 64 bits of storage? Imagine a future computer that allowed for 128-bit representations of integers. Has the space complex‐ ity changed? In Python, sys.getsizeof(...) determines the size in bytes for an object. Python 3 uses generators for range(), which significantly reduces the storage needs for Python programs. If you type the following statements into a Python inter‐ preter, you will see the corresponding storage requirements:

•    1 >>> import sys
     2 >>> sys.getsizeof(range(100))
     3 48
     4 >>> sys.getsizeof(range(10000))
     5 48
     6 >>> sys.getsizeof(list(range(100)))
     7 856
     8 >>> sys.getsizeof(list(range(1000)))
     9 8056
    10 >>> sys.getsizeof(list(range(10000)))
    11 80056
    12 >>> sys.getsizeof(list(range(100000)))
    13 800056
    14 
  

Здесь хорошо видно, что объём list(range(10000)) в байтах примерно в сто раз больше объёма list(range(100)). Глядя на остальные значения, можно с уверенностью сказать, что список в Python потребляет порядка O(N) памяти. These results show that the byte storage for list(range(10000)) is about 100 times larger than for list(range(100)). And when you review the other numbers, you can classify this storage requirement as O(N).

Для сравнения: и range(100), и range(10000) занимают один и тот же объём памяти — 48 байтов. Это новый для нас класс сложности, в котором значение постоянно и не зависит от N, он так и называется — константным. In contrast, the number of bytes required for range(100) and range(10000) is iden‐ tical (48 bytes). Since the storage is constant, we need to introduce another complex‐ ity class, known as the constant complexity class:

5. O(1) — константная сложность, где f(N)=c с некоторой постоянной c. O(1) is the constant complexity class, where f(N) = c for some constant c.

Ну что ж, в этой главе мы рассмотрели довольно много теоретического материала; настало время применить наши знания на практике. Пора изучить алгоритм оптимального поиска элемента в упорядоченном списке — по-научному он называется алгоритмом двоичного поиска в массивах. Мы выясним, отчего он так эффективен, и попутно познакомимся с новым, логарифмическим классом сложности O(log N). I’ve covered a lot of theoretical material in this chapter, and it’s time to put these con‐ cepts to practical use. I now present an optimal searching algorithm in computer sci‐ ence called Binary Array Search. In explaining why it is so efficient, I will introduce a new complexity class, O(log N).

Одна дверь захлопнулась — другая откроется

When One Door Closes, Another One Opens

За каждой из дверей на иллюстрации 2-4 скрыто по одному произвольному числу. Известно что числа за дверьми возрастают слева направо. Вопрос: сколько дверей необходимо в худшем случае открыть по одной, чтобы найти число 643 — или убедиться, что его за дверьми нет? Можно начать с самой левой и открывать каждую по очереди, пока не появится число 643 или большее (если 643 вообще не было за дверьми). Если не повезёт, придётся открыть все двери. В этом способе никак не учитывается, какие именно числа нашлись за уже открытыми дверями. В действительности для ответа на вопрос достаточно открыть не более трёх дверей. Для начала откроем дверь №4 — среднюю. I have written a sequence of seven different numbers in increasing order from left to right, and hidden each one behind a door, as shown in Figure 2-4. Try this challenge: what is the fewest number of doors you need to open—one at a time—to either find a target value of 643 or prove it is not hidden behind one of these doors? You could start from the left and open each door—one at a time—until you find 643 or a larger number (which means it wasn’t behind a door in the first place). But with bad luck, you might have to open all seven doors. This search strategy doesn’t take advantage of the fact that you know the numbers behind the doors are in ascending order. Instead, you can solve the challenge by opening no more than three doors. Start with door 4 in the middle and open it.

Иллюстрация 2-4. Двери Судьбы!

Там окажется число 173. Раз мы ищем 643, все двери слева от четвёртой нас больше не интересуют, потому что номера за ними меньше 173. Теперь откроем дверь №6 — за ней число 900. Прекрасно, теперь двери правее шестой нас тоже не интересуют. Остаётся только дверь №5 — и либо за ней скрывается 643, либо этого числа вообще не было в исходной последовательности. Пока она закрыта, мы волны воображать и то, и другое. The number it was hiding is 173; since you are searching for 643, you can ignore all of the doors to the left of door 4 (since the numbers behind those doors will all be smaller than 173). Now open door 6 to reveal the number 900. OK, so now you know that you can ignore the doors to the right of door 6. Only door 5 can be hiding 643, so open it now to determine whether the original series contained 643. I leave it to your imagination whether the number was behind that door.

На любой возрастающей последовательности из семи чисел и для любого искомого числа потребуется открыть не более трёх дверей. Кстати, можно заметить, что 2³ - 1 = 7. А если возрастающая последовательность будет состоять из миллиона элементов за миллионом дверей, и с нами поспорят на 10 000 долларов, что мы не найдём нужное число, открыв только 20 дверей? Надо соглашаться! Ведь 2²⁰=1048575, так что двадцати открытых дверей хватит на то, чтобы проверить возрастающую последовательность из 1 048 575 чисел. Более того, если количество дверей внезапно удвоится (даже дойдёт до 2 097 151), понадобится дополнительно открыть всего одну дверь, 21 дверь на все два с лишним миллиона. Удивительно быстрый способ! Вот мы и изобрели алгоритм двоичного поиска в упорядоченном массиве. If you repeat this process on any ascending list of seven numbers using any target value, you will never need to open more than three doors. Did you notice that 23 – 1 = 7? What if you had 1,000,000 doors covering an ascending list of numbers? Would you accept a $10,000 challenge to determine whether a specific number is hidden behind some door if you are only able to open 20 doors? You should! Since 220 – 1 = 1,048,575, you can always locate a number in an ascending list of 1,048,575 numbers after opening 20 or fewer doors. Even better, if there were suddenly twice as many doors, 2,097,151 in fact, you would never need to open more than 21 doors to find a number; that’s just one additional door to open. That seems astonishingly efficient! You have just discovered Binary Array Search.

Двоичный поиск в упорядоченном массиве

Binary Array Search

Двоичный поиск — один из базовых алгоритмов: порядок его сложности отличается от уже рассмотренных нами. В примере 2-3 реализован двоичный поиск значения target в упорядоченном списке A. Binary Array Search is a fundamental algorithm in computer science because of its time complexity. Listing 2-3 contains an implementation that searches for target in an ordered list, A.

   1 def binary_array_search(A, target):
   2   lo = 0
   3   hi = len(A) - 1               # 1
   4 
   5   while lo <= hi:               # 2
   6     mid = (lo + hi) // 2        # 3
   7 
   8     if target < A[mid]:         # 4
   9       hi = mid-1
  10     elif target > A[mid]:       # 5
  11       lo = mid+1
  12     else:
  13       return True               # 6
  14 
  15   return False                  # 7

• Пример 2-3. Двоичный поиск Listing 2-3. Binary Array Search

• Будем вести поиск в списке от индекса lo до индекса hi включительно. Поначалу они равны 0 и len(A)-1 соответственно. Set lo and hi to be inclusive within list index positions of 0 and len(A)–1.

• Цикл закончится, когда диапазон опустеет. Continue as long as there is at least one value to explore.

• В диапазоне A[lo … hi] найдём середину и значение A[mid] в ней. Find midpoint value, A[mid], of remaining range A[lo .. hi].

• Если target меньше A[mid], продолжим поиск слева от середины. If target is smaller than A[mid], continue looking to the left of mid.

• Если target больше A[mid], продолжим поиск спра от середины. If target is larger than A[mid], continue looking to the right of mid.

• Если это и есть target, вернём True. If target is found, return True.

• Если lo превысило hi, значит искать больше негде. Вернём False в знак того, что target не найден в A. Once lo is greater than hi, there are no values remaining to search. Report that target is not in A.

Поначалу lo и hi равны наименьшему и наибольшему индексу в A. Пока диапазон поиска не исчерпан, с помощью целочисленного деления находим его середину, mid. Если A[mid] и есть target, поиска окончены; иначе становится понятно, сужать ли диапазон до левой части, A[lo … mid-1] или до правой, A[mid+1 … hi]. Initially lo and hi are set to the lowest and highest indices of A. While there is a sub‐ list to explore, find the midpoint, mid, using integer division. If A[mid] is target, your search is over; otherwise you have learned whether to repeat the search in the sublist to the left, A[lo .. mid-1], or to the right, A[mid+1 .. hi].

Запись A[lo … mid] в нашей книге означает диапазон значений из списка A начиная с индекса lo до индекса mid включительно. Если lo < mid, диапазон пуст.

Наша функция определяет, принадлежит ли некоторое значение упорядоченному списку из N элементов. На каждом обороте цикла можно либо отыскать нужный элемент, либо сузить диапазон. Цикл заканчивается, когда элемент найден, или когда hi оказывается меньше lo. This algorithm determines whether a value exists in a sorted list of N values. As the loop iterates, eventually either the target will be found or hi crosses over to become smaller than lo, which ends the loop.

Немногим сложнее, чем π

Almost as Easy as π

Рассмотрим двоичный поиск числа 53 в списке на иллюстрации 2-5. Переменные hi и lo поначалу совпадают с границами списка A. В цикле while вычисляется mid. Поскольку A[mid] равно 19 и меньше 53, выполнение идёт по ветке elif и значение lo меняется на mid + 1. Дальнейший поиск производится уже по диапазону A[mid+1 … hi]. Серым закрашены не рассматриваемые значения. Размер диапазона уменьшается вполовину (с 7 до 3). Consider using Binary Array Search to find a target value of 53 in the list shown in Figure 2-5. First, set lo and hi to the boundary index positions of A. In the while loop, mid is computed. Since A[mid] is 19—which is smaller than the target, 53—the code takes the elif case, setting lo to mid + 1 to refine the search on the sublist A[mid+1 .. hi]. The grayed-out values are no longer in consideration. The size of the sublist being explored after this iteration is reduced by half (from 7 values to 3).

Иллюстрация 2-5. Поиск числа 53

На втором проходе цикла while вычисляется новое mid и оказывается что A[mid] равно искомому числу, 53, так что функция возвращается True. In the second pass through the while loop, mid is recomputed, and it turns out that A[mid] is 53, which is the target value, so the function returns True.

Имеет ли смысл перед запуском двоичного поиска поверить, точно ли A[0] <= target <= A[-1]? Так мы могли бы избежать бессмысленного поиска числа, которое в принципе не может оказаться в списке. Говоря коротко — нет, не имеет. Это добавит целых две проверки (которых даже на миллион всего двадцать) к каждому поиску, а сами проверки окажутся лишними в поиске чисел, которые заведомо принадлежат диапазону значений A.

Давайте теперь поищем число 17, которого нет в списке. Как показано на иллюстрации 2-5, lo и hi снова установлены по границам A. A[mid] равно 19; это больше, чем 17, так что вычисление идёт по ветке if, и диапазон сужается до A[lo … mid-1]. Серым закрашены значения, которые нам больше не нужны. A[mid] теперь равно 14, это меньше 17, и вычисление идёт по ветке elif, а диапазон сужается до A[mid+1 … hi]. Now let’s search for a value that is not in the list. To search for the target value of 17 in Figure 2-6, initialize lo and hi as before. A[mid] is 19, which is larger than the target, 17, so take the if case and focus the search on A[lo .. mid-1]. The grayed-out val‐ ues are no longer in consideration. The target, 17, is greater than A[mid] = 14, so take the elif case and try searching A[mid+1 .. hi].

Иллюстрация 2-6. Поиск числа 17

На третьем проходе цикла while получаем A[mid] равным 15; это меньше, чем искомое 17. Снова идём по ветке elif, где lo делается больше, чем hi: диапазон «схлопывается», как показано в конце иллюстрации 2-6. Условие цикла while становится ложным, и возвращается False: это означает, что target не найден в A. In the third time through the while loop, A[mid] is 15, which is smaller than the tar‐ get value of 17. Once again, take the elif case, which sets lo to be larger than hi; this is the “crossover,” shown at the bottom of Figure 2-6. The condition of the while loop is false, and so False is returned, declaring that A does not contain the target value.

Двух зайцев одним выстрелом

Two Birds with One Stone

Зачастую требуется найти, где именно в A находится target, а не только проверить, что он там есть. Пока что наша функция возвращала только True или False. Слегка подправим исходный текст, и двоичный поиск будет возвращать позицию mid, где находится target. What if you want to know the exact location of target in A, instead of just confirm‐ ing that target is contained in A? Binary Array Search currently returns True or False. Modify the code, as shown in Listing 2-4, to return the index position, mid, where target is found.

   1 def binary_array_search(A, target):
   2   lo = 0
   3   hi = len(A) - 1
   4 
   5      while lo <= hi:
   6        mid = (lo + hi) // 2
   7 
   8       if target < A[mid]:
   9         hi = mid-1
  10       elif target > A[mid]:
  11         lo = mid+1
  12       else:
  13         return mid              # 1
  14 
  15      return -(lo+1)             # 2

• Пример 2-4. Вычисление позиции target в A Listing 2-4. Return location of target in A

• Возвращаем mid, потому что именно там мы нашли target. Return the value of mid since that is the location of target.

• Уведомляем пользователя о том, что targat не найден, возвращая отрицательный индекс -lo - 1. Alert caller that target doesn’t exist by returning the negative of lo + 1.

Что бы такого полезного вернуть, если target нет в A? Можно просто None, как это принято в Python, но в нашем случае есть шанс дать пользователю дополнительный сведения. Например, можно не только сообщить о том, что target отсутствует в A, но и заранее вычислить место, куда его следует при необходимости вставить, не нарушая порядка A. What should be returned when target is not in A? You could just return –1 (which is an invalid index location), but there is an opportunity to return more information. What if we could tell the caller “target is not in A, but if you wanted to insert target into A, it would go in this location”?

Давайте ещё раз посмотрим на иллюстрацию 2-6. Пока мы искали число 17 в списке, где его не было, значение lo стало указывать на место, куда 17 можно было бы вставить, соблюдая порядок в A. Можно было бы в этом случае вернуть просто -lo, но если искомый элемент найден в начальной позиции, или не найден, и это только место вставки, в обоих случаях вернётся 0 . Так что возвращаем заведомо отрицательное число -(lo + 1). Если пользователь получит отрицательное x, он будет знать, что target отсутствует в A, но его можно туда добавить в позицию -(x + 1). Если x неотрицателен — это позиция target в A. Look at Figure 2-6 again. When searching for a target value of 17 (which doesn’t exist in A), the final value of lo is actually where 17 would be inserted. You could return –lo as the result, and this would work for all index locations except for the first one, which is zero. Instead return the negation of (lo + 1). The calling function that receives a negative value, x, has learned that target would be placed at location –(x + 1). When a nonnegative value is returned, that is the location of target in A.

Напоследок — ещё немного оптимизации. В примере 2-4 над элементами A производится два сравнения, хотя можно было бы обойтись одним, а потом проверять его результаты. Если значения числовые, таким сравнением может быть их разность — как в примере 2-5, где над элементами A производится всего одно действие (а не два). Кстати, операция индексирования A[mid] в примере тоже одна. One final optimization remains. In Listing 2-4, there are two comparisons between target and A[mid]. When both values are numeric, Listing 2-5 shows how to com‐ pute their difference just once instead of invoking this key operation twice; this also ensures you only access A[mid] once.

   1 diff = target - A[mid]
   2 if diff < 0:
   3   hi = mid-1
   4 elif diff > 0:
   5   lo = mid+1
   6 else:
   7   return mid

• Пример 2-5. Оптимизация, которая требует только одного сравнения элементов списка Listing 2-5. Optimization that requires just a single value comparison

Если target был меньше A[mid], diff окажется отрицательным, и это аналогично сравнению target < A[mid]. Если diff положителен, значит, target оказался больше A[mid]. Допустим, значения A — не числовые, но для них существует операция сравнения, которая возвращает отрицательное число, ноль или положительное число, в соответствии с тем, как эти значения можно упорядочить. Сравнение обычных целых вместо дорогостоящего сравнения элементов увеличивает быстродействие. If target is smaller than A[mid], then diff < 0, which is equivalent logically to checking whether target < A[mid]. If diff is positive, then you know target was greater than A[mid]. Even when the values are not numeric, some programming lan‐ guages offer a compareTo() function that returns a negative number, zero, or a posi‐ tive number based on the relative ordering of two values. Using this operation leads to more efficient code when comparison operations are costly.

Если список упорядочен по убыванию, двоичный поиск тоже работает — только hi и lo должны в цикле while меняться по-другому.

Как быстро работает двоичный поиск на данных объёма N? Чтобы ответить на вопрос, надо привести наихудший случай входных данных и посчитать, сколько раз должен выполниться цикл while. Понятие «логарифма» нам в помощь!¹² How efficient is Binary Array Search on a problem instance of size N? To answer this question, I have to compute, in the worst case, how many times the while loop is forced to execute. The mathematical concept of logarithms will tell us the answer.5

Что такой логарифм? Попробуем ответить на вопрос: сколько раз нужно удвоить единицу, чтобы получить число 33 554 432? Можно, конечно, попробовать добраться до него вручную — 1, 2, 4, 8, 16 и т. д. — но это довольно скучно. Что мы ищем, с математической точки зрения? Такое x, что 2^x=33554432. To see how logarithms work, consider this question: how many times do you need to double the number 1 until the value equals 33,554,432? Well, you could start comput‐ ing this manually: 1, 2, 4, 8, 16, and so on, but this is truly tedious. Mathematically, you are looking for a value, x, such that 2x = 33,554,432.

Запись 2^x — это возведение основания 2 в степень x. Логарифм — функция, обратная возведению в степень, примерно как деление — функция, обратная умножению. Чтобы найти такое x, что 2^x=33554432, надо посчитать логарифм по основанию 2 от этого числа, log₂ 33554432. Получится 25.0. Если вычислить 2²⁵ на калькуляторе, получится 33 554 432.

Note that 2x involves exponentiation of a base (the value 2) and an exponent (the value x). A logarithm is the opposite of exponentiation, in the same way that division is the opposite of multiplication. To find an x such that 2x = 33,554,432, compute log2 (33,554,432) using a base of 2, resulting in the value 25.0. If you type the equation 225 into a calculator, the result is 33,554,432.

То же значение — ответ на вопрос «как долго можно делить 33554432 пополам?»: после 25 делений получится 1. Логарифм — вещественное число; например, log₂ 137 — примерно 7.098032. Что в целом понятно: раз уж 2⁷=128, то для получения 137 степень нужна чуть-чуть побольше. This computation also answers the question of how many times you can divide 2 into 33,554,432. You get to 1 after 25 divisions. log() computes a floating point result; for example, log2(137) is about 7.098032. This makes sense since 27 = 128, and 137 would require a slightly higher exponent for base 2. переведённая сноска 5 It is purely a coincidence that the word logarithm is an anagram of algorithm.

В алгоритме двоичного поиска цикл while повторяется до тех пор, пока lo ⩽ hi — то есть пока есть где искать. На первом проходе в диапазоне поиска N значений, на втором их уже N/2 (а если N нечётно, то (N-1)/2). Следовательно, чтобы предсказать количество проходов цикла, надо посчитать, сколько раз придётся делить N пополам, пока не получится 1. А это и есть в точности k = log₂ N, что даёт нам 1 + k проходов цикла (первый — для полного N, остальные k — для меньших диапазонов). Логарифм — вещественное число, нам для оценки количество проходов, конечно, нужно целое. Подойдёт нижнее округление floor(x), математическая функция, возвращающая наибольшее целое число, не превосходящее x¹³ The Binary Array Search algorithm will repeat the while loop as long as lo ≤ hi, or in other words, while there are values to search. The first iteration starts with N values to search, and in the second iteration, this is reduced to no more than N/2—if N is odd it is (N – 1)/2. To determine the maximum number of successive iterations, you need to know how many times you can divide N by 2 until you reach 1. This quantity is exactly k = log2(N), so the total number of times through the while loop is 1 + k, counting 1 for the first time for N values plus k for the successive iterations. Because log() can return a floating point value, and we need an integer number for the number of iterations, use the floor(x) mathematical operation, which computes the largest integer that is smaller than or equal to x.

No handheld calculator has a button to compute log2(X)—most calculator apps don’t either. Don’t panic! You can always compute log2 easily. For example, log2(16) = 4. On your calculator, enter 16 and then press the log button (which is either in base 10 or the nat‐ ural base e). Your display should read something awful like 1.20411998. Now press the / (divide) button, press the 2 button, and finally press the log button again. Your display should read 0.301029995. Now that all hope seems lost, press the equals button. Magically the value 4 appears. This sequence of operations demon‐ strates that log2(X) = log10 (X)/log10 (2).

Прямо испанский стыд какой-то! А можно эту выноску в перевод не включать? Портативные микрокалькуляторы… Если надо ещё раз объяснить про смену основания логарифма, я лучше на примере Python покажу! Примерно так:

Далеко не каждый калькулятор или приложение-калькулятор умеют вычислять двоичный логарифм. Но у нас же есть Python! Лучший в мире программируемый калькулятор всегда у вас под рукой. Достаточно запустить любую версию командного интерпретатора — стандартный python, консоль любого средства разработки (например, IDLE — она есть в базовой поставке python) или специализированный терминал, наподобие iPython — и импортировать нужную библиотеку. В ответ на подсказку «>>> » вводим нужную формулу — и вуаля, ответ перед нами.

   1 >>> from math import *
   2 >>> log2(16)
   3 4.0
   4 >>> log(16)
   5 2.772588722239781
   6 >>> log10(16)
   7 1.2041199826559248
   8 >>> log(16)/log(2)
   9 4.0
  10 >>> log10(16)/log10(2)
  11 4.0
  12 

-- FrBrGeorge 2021-12-15 09:03:52

Итак, в двоичном поиске цикл while делает не более floor(log2(N))+1 проходов. Это невероятно быстро! Найти нужное число из миллиона отсортированных значений можно всего за 20 попыток. For Binary Array Search, the while loop iterates no more than floor(log2(N)) + 1 times. This behavior is truly extraordinary! With one million values in sorted order, you can locate any value in just 20 passes through the while loop.

Мы можем сами убедиться в корректности формулы: для любого объёма входных данных от 8 до 15 элементов требуется не более 4 проходов. Если на первом проходе в диапазоне 15 элементов, то на втором их будет 7, на третьем — 3, и на четвёртом останется только один. Если начать с 10 элементов, диапазон будет меняться так: 10 → 5 → 2 → 1 — и это тоже четыре прохода.

Получается, что изучение двоичного поиска дало нам новый класс сложности, O(log(N)), он называется логарифмическим, потому что определяющая его функция f(N) = log(N). The experience with Binary Array Search leads to a new complexity class, O(log N), called the logarithmic complexity class, where f(N) = log(N).

Стало быть, если при изучении алгоритма мы утверждаем, что его сложность по времени — O(log N), это означает, что существует такая константа c, для которой, начиная с некоторого достаточно большого N, скорость работы алгоритма T(N) будет всегда меньше, чем c · log N. Наше утверждение верно, если неверны аналогичные утверждения относительно более низких классов вычислительной сложности. To summarize, when you analyze an algorithm and state that its time complexity is O(log N), you are claiming that once the problem instance size is larger than some threshold size, the runtime performance, T(N), of the algorithm is always smaller than c × log(N) for some constant, c. Your claim is correct if you can’t make this claim with another complexity class of lower complexity. All complexity classes are arranged in order of dominance, as shown in Figure 2-7.

Иллюстрация 2-7. Иерархия классов вычислительной сложности в порядке доминирования

У автора — «всех классов», но потом он сам говорит, что это неправда, и тут даже не все описанные в книге классы сложности есть, не говоря о массе других.

Термин sublinear и по-русски (сублинейные), и по-английски имеет совсем другое основное значение.

И ещё. Вот эта стрелка вниз как бы намекает нам о существовании алгоритмов, которые эффективнее, чем O(1), т. е. выдают решение быстрее, чем сразу. Надо бы её убрать, или как минимум задизайнить так, чтобы не показывала вниз от O(1).

• -- FrBrGeorge 2021-12-16 08:20:13

Классов вычислительной сложности в теории бесконечно много, но на практике вот эти восемь встречаются чаще всего. Константное время выполнения, O(1) — это низший класс сложности, при этом время работы алгоритма постоянно и не зависит от размера входных данных. Следующий класс в иерархии — O(log N), логарифмический, мы уже видели, что двоичный поиск относится к этой категории. Оба эти класса — долинейные, она содержат чрезвычайно эффективные алгоритмы. While there are an infinite number of complexity classes, the eight classes in this fig‐ ure are the most commonly used ones. The constant time, O(1), has the least amount of complexity and reflects constant work that is independent of the size of the prob‐ lem instance. The next-higher complexity class, O(log N), is logarithmic, and you have seen how Binary Array Search falls into this category. Both of these classes are sub-linear and result in extremely efficient algorithms.

Линейная сложность, O(N), предусматривает увеличение времени работы прямо пропорционально объёму данных. Далее идёт набор полиномиальных классов в порядке возрастания сложности — O(N²), O(N³) и так далее вплоть до любой наперёд взятой константы c, O(N^c)¹⁴. Между O(N) и O(N²) затесался класс O(N log N); для многих задач именно алгоритм такого класса специалисты считают наилучшим. The linear, O(N), complexity class means complexity is directly proportional to the size of the problem instance. A series of polynomial classes are all of increasing com‐ plexity—O(N2), O(N3), and so on—up to any fixed constant, O(Nc). Sandwiched between O(N) and O(N2) is O(N log N), which is often identified as the ideal com‐ plexity class for algorithm designers.

Доминирование классов друг над другом выражается ещё и в том, как определяется алгоритм, в оценке сложности которого встречаются несколько различных компонентов-формул. Например, если сложность одной части алгоритма оценивается как O(N log N), а другой — как O(N²), то какова сложность всего алгоритма? Ответ — O(N²), потому что сложность второй части доминирует над сложностью первой. Если, например, оценка сложности вашего алгоритма T(N) оказалась равной 5 N² + 10000000·N·log₂ N, то класс его сложности — O(N²). This dominance hierarchy can also help identify how to classify an algorithm when there is a mixed combination of time complexities. For example, if an algorithm con‐ tains two substeps—the first with time complexity of O(N log N) and the second with O(N2)—what is its overall complexity? The overall classification of the algorithm is O(N2) because the complexity of substep 2 is the dominant impact on the overall complexity. In practical terms, if you have modeled T(N) for an algorithm to be 5N2 + 10,000,000 × N × log(N), then T(N) has complexity of O(N2).

Два оставшихся класса в иерархии — экспоненциальный и факториальный — описывают весьма неэффективные алгоритмы, которые могут работать только очень небольшим числом данных. Тренировочное задание в конце этой главы посвящено в том числе и этим классам сложности. The final two complexity classes—exponential and factorial—are inefficient, and algorithms with these time complexities can only solve very small problem instances. Check out the challenge exercises at the end of the chapter that address these com‐ plexity classes.

Как всё это работает

Pulling It All Together

В таблице 2-4 представлены результаты вычислений f(N) для каждого упомянутого класса сложности. Предположим, что числа в таблице — это время работы некоторого алгоритма в секундах. Сложность алгоритма указана в заголовке столбца, а размер входного набора данных N — в заголовке строки. 4096 минут — это час и восемь минут, так что чуть больше, чем за час можно решить: Table 2-4 presents the computation of f(N) for each of the designated complexity classes. Imagine that each of these numbers represents the estimated time in seconds for an algorithm with the rated time complexity (in a column) to process a problem instance of size N (as identified by the row). 4,096 is about one hour and eight minutes, so in just over an hour of computation time, you could likely solve:

• Любую задачу сложности O(1), потому что размер входных данных в ней не имеет значения; An O(1) algorithm, since its performance is independent of the problem instance size

• Задачу сложности O(log N) на входном наборе размером не более, чем 2⁴⁰⁹⁶; An O(log N) algorithm for problem instances of size 24096 or smaller

• Задачу сложности O(N) на входном наборе размером не более, чем 4096; An O(N) algorithm for problem instances of 4,096 or smaller

• Задачу сложности O(N log N) на входном наборе размером не более, чем 462; An O(N log N) algorithm for problem instances of size 462 or smaller

• Задачу сложности O(N²) на входном наборе размером не более, чем 64; An O(N2) algorithm for problem instances of size 64 or smaller

• Задачу сложности O(N³) на входном наборе размером не более, чем 16; An O(N3) algorithm for problem instances of size 16 or smaller

• Задачу сложности O(2^N) на входном наборе размером не более, чем 12; An O(2N) algorithm for problem instances of size 12 or smaller

• Задачу сложности O(N!) на входном наборе размером не более, чем 7. An O(N!) algorithm for problem instances of size 7 or smaller

• Таблица 2-4. Рост различных оценок сложности. Table 2-4. Growth of different computations

Нужно стараться отыскать алгоритм с самым низким классом сложности, потому что, как это показано на иллюстрации 2-8, всегда может попасться задачка, в которой и для самого быстрого компьютера данных слишком много. А алгоритмы высокого уровня сложности даже на малых объёмах данных могут работать практически бесконечно. The reason to investigate algorithms with the lowest complexity rating is because the problems you want to solve are simply too large on even the fastest computer. With higher complexity classes, the time to solve even small problems essentially is infinite (as Figure 2-8 shows).

Иллюстрация 2-8. График быстродействия разных классов сложности на возрастающем объёме входных данных

Быстродействие различных классов на больших объёмах данных выглядит обычно так, как на иллюстрации 2-8. Ось X отвечает за размер входного набора, ось Y — за полное время работы алгоритма, классы алгоритмов надписаны на графиках. Чем выше класс сложности алгоритма, тем меньше объём данных, которые он сможет обработать за «приемлемое время»¹⁵. A common way to visualize these extremely large numbers is shown in Figure 2-8. The x-axis represents the size of the problem instance being solved. The y-axis repre‐ sents the total estimated runtime performance for one of the algorithms labeled in the chart. As the complexity of the algorithm increases, the size of the problem instance that can be solved “in reasonable time” decreases.

Рассмотрим ещё несколько примеров посложнее: Consider the following, more complex scenarios:

• Если сложность алгоритма оценивается как O(N² + N) — к какому классу его отнести? Согласно иерархии на иллюстрации 2-7 N² доминирует над N, и следовательно, оценку можно упростить до O(N²). По тем же соображениям O(2^N+N⁸) упрощается до O(2^N). If someone classifies an algorithm as O(N2 + N), how should you respond? The dominance hierarchy in Figure 2-7 shows that N2 has a greater complexity than N, and so this can be simplified to be O(N2). Similarly, O(2N + N8) would be sim‐ plified to become O(2N).

• Если сложность оценивается как O(50·N³), оценка упрощается до O(N³), потому что мултипликативная постоянная значения не имеет. If an algorithm is classified as O(50 × N3), you can simplify this to become O(N3) because multiplicative constants can be eliminated.

• Иногда быстродействие алгоритма зависит не только от размера входных данных N, но и от их свойств. Скажем, имеется алгоритм, на первом шаге которого N числовых значений отрабатывается за линейное время (т. е. за время ,прямо пропорциональное N). На втором шаге этого алгоритма из входных данных обрабатываются только чётные числа, и время этой обработки пропорционально E² (где E — количество чётных чисел во входном наборе). Если походить к вопросу аккуратно, оценка получится O(N + E²). Допустим, чётные числа не очень-то и нужны, и для решения задачи достаточно входного набора без них. Тогда оценка упадёт до O(N), что может быть весьма полезно. Понятное дело, худший случай для такого алгоритма — это набор исключительно чётных чисел, так что общая оценка будет O(N²) (поскольку E ⩽ N). Sometimes the behavior of an algorithm can depend on properties other than just the size of the problem instance, N. For example, consider an algorithm that processes N numeric values, with a primary task whose runtime performance is directly proportional to N. Now assume this algorithm has a subtask that pro‐ cesses all even values in the problem instance. The runtime performance of this subtask is directly proportional to E2, where E represents the number of even val‐ ues. You might want to carefully specify that the runtime performance of the algorithm is O(N + E2). If, for example, you could eliminate all even values from the input set, this performance would be rated as O(N), and that might be note‐ worthy. Naturally, in the worst case where all numbers are even, then the overall classification of the algorithm would become O(N2) since E ≤ N.

Приближённая кривая — или чёткие границы?

Curve Fitting Versus Lower and Upper Bounds

В пакете SciPy есть функция curve_fit(), которая с помощью нелинейного метода наименьших квадратов может подобрать коэффициенты для некоторой модельной функции f, чтобы та как можно лучше описывала имеющиеся данные. Мы использовали её, когда для измеренного на разных объёмах данных N времени работы алгоритма прикидывали, какой функцией оно может выражаться. Как мы уже знаем, curve_fit() возвращает коэффициенты, подставив которые в f мы получим приближение с минимальной суммой квадратов отклонений значений этой функции от имеющихся данных. The curve_fit() function provided by SciPy uses a nonlinear, least squares method to fit a model function, f, to existing data. I use data based on different problem instances of size N and the respective runtime performance of an algorithm in solv‐ ing those instances. The result of curve_fit()—as you have seen in this chapter—are coefficients to use with a model function to predict future runtime performance. With these coefficients applied to f, the resulting model minimizes the sum of the square of the errors between the actual data and the predicted value from the model.

Таким способом можно довольно точно угадать, как будет себя вести конкретная реализация алгоритма на других наборах данных в исследованном нами диапазоне. Однако само по себе наше приближение не может выступать ни в роли верхней, ни в роли нижней границы оценки сложности. Для точной оценки надо оценить количество действий, которые выполняет данная реализация алгоритма, именно оно управляет временем работы — и на этом основании уже делать предположения. These are useful to get a ballpark estimate of the inner behavior of an algorithm’s implementation on specific problem instances. By itself, this model is neither a pro‐ ven upper bound or lower bound regarding the complexity of an algorithm. You need to review the algorithm’s implementation to develop a model that counts the number of key operations, which directly affects the runtime performance of the algorithm.

Построив функцию f(N), которая оценивает количество выполняемых действий на наборе данных размера N в худшем случае, мы можем оценить сложность алгоритма как O(f(N()) в худшем случае — и это будет верхняя граница. Соответствующую нижнюю границу можно вывести из функции g(N), оценивающей минимально возможное количество действий в лучшем случае — эта граница обозначается как Ω(g(N)).¹⁶ When you have an accurate model, f(N), that reflects the count of the key operations in the worst case for an algorithm on a problem instance of size N, then you have clas‐ sified O(f(N)) in the worst case. This is the upper bound. A corresponding lower bound can be similarly derived to model the effort that the algorithm must at least expend in the worst case. The notation Ω(f(N)) is used to describe the classification of the lower bound of an algorithm.6

В разговоре про двоичный поиск мы выяснили, что цикл while в функции делает не более floor(log2(N)) + 1 проходов. Это значит, что оценка в худшем случае f(N) = log(N), и порядок сложности двоичного поиска — логарифмический, O(log(N)). Как двоичный поиск работает в лучшем случае? Если искать элемент, равный A[mid], функция завершится всего за один проход цикла. Этот результат постоянен и не зависит от размера входных данных, значит, порядок двоичного поиска в лучшем случае — константный, O(1). Обозначение «О большое» можно применять и для лучших, и для худших случаев, хотя с точки зрения большинства программистов это имеет смысл только для худших. In our earlier discussion of Binary Array Search, I demonstrated that the while loop iterates no more than floor(log2(N)) + 1 times. This means, in the worst case, use f(N) = log(N) to formally classify Binary Array Search as O(log N). What is the best case for Binary Array Search? If the target value is found in A[mid], the function returns after just one pass through the while loop. Since this is a constant independ‐ ent of the size of the problem instance, this means that Binary Array Search is classified as O(1) in the best case. The big O notation can be used for both best case and worst case analysis, although many programmers assume it is meant only for worst case.

Для классификации сложности алгоритма нередко применяют обозначение вида Θ(N log N) (с большой греческой буквой тета). Хотя чаще всего это обозначение применяется для оценки сложности алгоритма в среднем, его смысл более узкий. Такая запись означает, что и верхняя и нижняя граница оценки определяется одной и той же формулой, в данном случае верхняя граница — O(N log N), а нижняя — Ω(N log N). По-английски этот термин звучит как «tight bound», «строгая оценка». Строгая оценка производительности алгоритма, если она есть — лучший способ убедиться, что время его работы хорошо предсказуемо.

Заключение

Summary В первых двух главах книги мы продвинулись в изучении алгоритмов довольно далеко, но непройденных дорог намного больше. Мы видели достаточно примеров того, что быстродействие алгоритма не зависит от способа его реализации. Пока учёные середины двадцатого века изобретали новые алгоритмы, инженеры успешно повышали быстродействие самих компьютеров, на которых эти алгоритмы работают. Чтобы при изучении быстродействия алгоритмов не зависеть от производительности аппаратной платформы и вывести некоторые абсолютные оценки, мы применили основы асимптотического анализа. Мы рассмотрели несколько классов сложности (по времени или по памяти), которые приведены на иллюстрации 2-8, и с их помощью научились показывать, как производительность алгоритма зависит от объёма обрабатываемых данных. Классы сложности нам понадобятся и впредь, с их помощью можно коротко описать быстродействие алгоритма. We have covered a lot of ground in these first two chapters, but there is so much more you can learn about analyzing algorithms. I presented a number of examples that describe the way algorithms behave independent of how they are implemented. In the mid-20th century, while researchers were discovering new algorithms, advances in computing technology dramatically improved the very performance of the com‐ puters executing these algorithms. Asymptotic analysis provides the foundation for independently assessing the performance of algorithms in a way that eliminates any dependence on the computing platform. I defined several time (or storage) complex‐ ity classes, visualized in Figure 2-8, to explain the behavior of an algorithm in terms of the size of the problem instances. These complexity classes appear throughout the book as a notation to quickly summarize an algorithm’s behavior.

переведённая сноска 6 Ω is the capitalized Greek character omega.

Тренировочные задания

Challenge Exercises

1. Оцените сложность по времени каждого из фрагментов программы в таблице 2-5. Rate the time complexity of each code fragment in Table 2-5.

   • Фрагмент 1

        1    for i in range(100):
        2      for j in range(N):
        3        for k in range(10000):
        4          ...
     

   • Фрагмент 2

        1    for i in range(N):
        2      for j in range(N):
        3        for k in range(100):
        4          ...
     

   • Фрагмент 3

        1    for i in range(0,N,2):
        2      for j in range(0,N,2):
        3        ...
     

   • Фрагмент 4

        1    while N > 1:
        2      ...
        3      N = N // 2
     

   • Фрагмент 5

        1    for i in range(2,N,3):
        2      for j in range(3,N,2):
        3        ...
     

   Таблица 2-5. Оцените фрагменты программ Table 2-5. Code fragments to analyze

2. Используя методику анализа, описанную в этой главе, оцените значение ct, возвращаемое функцией f4(N) в примере 2-6. Use the techniques described in this chapter to model the value of ct returned by the f4 function in Listing 2-6.

      1  def f4(N):
      2    ct = 1
      3    while N >= 2:
      4      ct = ct + 1
      5      N = N ** 0.5
      6    return ct
   

   Пример 2-6. Исследуйте функцию Listing 2-6. Sample function to analyze

   • Ни одну из рассмотренных в данной главе оценок применить не получится. Попробуйте взять за основу формулу a · log₂(log₂N). Составьте таблицу значений функции вплоть до N = 2⁵⁰ и сравните с вашей оценкой. Полученный класс сложности можно определить как O(log(log N)).

   You will find that none of the models used in this chapter is accurate. Instead, develop one based on a × log(log(N)), in base 2. Generate a table up to N = 250 containing actual results as compared to the model. An algorithm with this behavior would be classified as O(log(log(N))).

3. Есть один неэффективный способ сортировки: перебрать все перестановки исходного массива и вернуть ту, которая окажется отсортированной. Этот способ приведён в примере 2-7. One way to sort a list of values is to generate each permutation until you find one that is sorted, as shown in Listing 2-7.

      1 from itertools import permutations, pairwise
      2 from scipy.special import factorial
      3 
      4 def factorial_model(v, a):
      5   return a * factorial(v)
      6 
      7 def check_sorted(a):
      8   for x, y in pairwise(a):
      9     if x > y:
     10       return False
     11   return True
     12 
     13 def permutation_sort(A):
     14   for attempt in permutations(A):
     15     if check_sorted(attempt):
     16       A[:] = attempt             # заполним A отсортированными значениями
     17       return
   

   Пример 2-7. Сортировка путём перебора всех перестановок списка Listing 2-7. Code to generate permutations from a list

   • Составьте таблицу быстродействия функции permutation_sort() в наихудшем случае (здесь это список, упорядоченный по убыванию); размер списка от 1 до 12 элементов включительно. Подберите приближённую кривую с помощью функции factorial_model() и исследуйте, насколько хорошо она прогнозирует время работы permutation_sort(). Сколько лет, если верить полученным данным, эта функция будет сортировать упорядоченный по убыванию список из 20 элементов?¹⁷ Generate a table of results for sorting a worst case problem instance (i.e., the val‐ ues are in descending order) of up to 12 elements using permutation_sort(). Use the factorial_model() to curve fit the preliminary results and see how accurate the model is in predicting runtime performance. Based on these results, what is your estimate (in years) for the runtime performance on a worst case problem instance of size 20?

4. Соберите данные по быстродействию 50 000 экспериментальных запусков двоичного поиска на случайных наборах размера N от 2⁵ до 2²¹. Каждый эксперимент должен использовать случайный входной набор размера N, получаемый с помощью random.sample() из диапазона чисел от 0 до 4·N, который затем нужно отсортировать. Искать в каждом эксперименте нужно случайное число из того же диапазона. Generate empirical evidence on 50,000 random trials of Binary Array Search for N in the range of 25 through 221. Each trial should use random.sample() to ran‐ domly select N values from the range 0 .. 4N and place these values in sorted order. Then each trial should search for a random target value in the same range.

   • Используя методику, описанную в данной главе, подберите с помощью curve_fit() логарифмическое (Log N) приближение к полученным данным для N в диапазоне от 2⁵ до 2¹². Определите пороговое значение N, начиная с которого результаты экспериментов предсказуемо описываются найденным приближением. Нарисуйте график функции-приближения и точки экспериментальных данных. Насколько достоверно найденная функция описывает эксперимент? Using the results I have outlined in this chapter, use curve_fit() to develop a log N model that models the results of runtime performance for N in the range 25 through 212. Determine the threshold problem instance size above which the behavior stabilizes. Create a visual plot of the data to see whether the computed model accurately models the empirical data.

5. В отличие от предыдущих задач, будем исследовать сложность по памяти. Рассмотрим ещё один странный алгоритм сортировки списка в примере 2-8. We are normally concerned with time complexity, but consider the sorting algo‐ rithm in Listing 2-8:

      1      def max_sort(A):
      2        result = []
      3        while len(A) > 1:
      4          index_max = max(range(len(A)), key=A.__getitem__)
      5          result.insert(0, A[index_max])
      6          A = list(A[:index_max]) + list(A[index_max+1:])
      7        return A + result
   

   • Пример 2-8. Сортировка путём постоянного удаления наибольшего значения из списка Listing 2-8. Code to sort by repeatedly removing maximum value from list

   • Используя методику из этой главы, оцените сложность по памяти функции max_sort(). Using the results I have outlined in this chapter, assess the storage complexity of max_sort.

6. Галактический алгоритм — это алгоритм решения некоторой задачи, который становится эффективнее других известных алгоритмов только на «недостижимо большом» наборе данных. Например, алгоритм умножения N-значных чисел, опубликованный в ноябре 2020 года Дэвидом Харви и Йорисом ван дер Хувеном, имеет сложность O(N log N), но только для N, превышающих 2^Z, где Z = 1729¹². Это Z — само по себе астрономическое число, примерно 7·10³⁸, а уж если в такую степень возвести 2, получится уже что-то запредельно громадное! Почитайте, что пишут о галактических алгоритмах. На практике их использовать нельзя, но зачастую осознание того, что для данной задачи может существовать алгоритм более низкого класса сложности, подталкивает к дальнейшим открытиям! A galactic algorithm is an algorithm whose time complexity is better than any known algorithm when the problem instance size is “sufficiently large.” For example, the N-digit multiplication algorithm (published November 2020) by David Harvey and Joris Van Der Hoeven has O(N log N) runtime performance, once N is larger than 2Z, where Z is 172912; this exponent, Z, is already an astro‐ nomically large number, about 7 × 1038. Consider now raising 2 to this incredibly large number! Do some research on other galactic algorithms. While these algo‐ rithms are not practical, they do offer hope that breakthroughs are possible on some really challenging problems.

7. В таблице 2-1 приведены три ряда измерения для трёх размеров набора входных данных. Если бы рядов было только два, удалось бы составить приближение для квадратичного алгоритма? Более общий вопрос: если имеется K замеров производительности, какова наибольшая степень многочлена, которым можно приблизить эти результаты? Table 2-1 contains three rows of performance measurements on three data sets of different sizes. If you only had two rows of performance measurements, would it be possible to predict the performance of a quadratic time algorithm? In general, if you have K rows of performance measurements, what is the highest polynomial you can effectively use in a model?