Примож Габриэльчич - Высокая производительность Delphi (черновик перевода глав 1-2)

which is quite a hit. Such algorithms are typically not very useful if we have to process large amounts of data.

Если сложность алгоритма равна O(n²), увеличение размера данных в 10 раз приведет к тому, что алгоритм будет работать в 10² или 100 раз дольше. Если мы хотим обработать в 1 000 раз больше данных, то алгоритм займет в 1 000² или в миллион раз больше времени, что является настоящим ударом. Такие алгоритмы, как правило, не очень полезны, если нам приходится обрабатывать большие объемы данных.

Most of the time, we use the Big O notation to describe how the computation time relates to the input data size. When this is the case, we call the Big O notation time complexity. Nevertheless, sometimes the same notation is used to describe how much storage (memory) the algorithm is using. In that case, we are talking about a space complexity.

Большую часть времени мы используем обозначение Big O, чтобы описать, как время вычисления связано с размером входных данных. Когда это так, мы называем нотацию Big O временно́й сложностью. Тем не менее, иногда та же нотация используется для описания объема хранилища (памяти), используемого алгоритмом. В этом случае мы говорим о пространственной сложности.

You may have noticed that I was using the word average a lot in the last few paragraphs. When talking about the algorithm complexity, we are mostly interested in the average behavior, but sometimes we will also need to know about the worst behavior. We rarely talk about best behavior because users don't really care much if the program is sometimes faster than average.

Возможно, вы заметили, что в последних нескольких абзацах я часто использовал слово «средний». Когда мы говорим о сложности алгоритма, нас в основном интересует среднее поведение, но иногда нам также нужно будет знать о наихудшем поведении. Мы редко говорим о лучшем поведении, потому что пользователям на самом деле все равно, если программа иногда работает быстрее, чем в среднем.

Let's look at an example. The following function checks whether a string parameter value is present in a string list:

Давайте рассмотрим пример. Следующая функция проверяет, присутствует ли значение строкового параметра в списке строк:

function IsPresentInList(strings: TStrings; const value: string): Boolean;

var

   i: Integer;

begin

   Result := False;

   for i := 0 to strings.Count - 1 do

      if SameText(strings[i], value) then

         Exit(True);

end;

What can we tell about this function? The best case is really simple—it will find that the value is equal to strings[0] and it will exit. Great! The best behavior for our function is O(1). That, sadly, doesn't tell us much as that won't happen frequently in practice.

Что мы можем сказать об этой функции? В лучшем случае все действительно просто — она обнаружит, что значение равно strings[0], и завершит работу. Отлично! Наилучшее поведение для нашей функции — O(1). Это, к сожалению, не говорит нам о многом, так как на практике такое случается нечасто.

The worst behavior is also easy to find. If the value is not present in the list, the code will have to scan all of the strings list before deciding that it should return False. In other words, the worst behavior is O(n), if the n represents the number of elements in the list. Incidentally (and without proof), the average behavior for this kind of search is also O(n).

Худшее поведение также легко найти. Если value отсутствует в списке, код должен будет просканировать весь список строк, прежде чем решить, что он должен вернуть значение False. Другими словами, наихудшее поведение — O(n), если n представляет количество элементов в списке. Кстати (и без доказательств), среднее поведение для такого рода поиска также равно O(n).

The Big O limits don't care about constant factors. If an algorithm would use n/2 steps on average, or even just 0.0001 * n steps, we would still write this down as O(n). Of course, a O(10 * n) algorithm is slower than a O(n) algorithm and that is absolutely important when we fine-tune the code, but no constant factor C will make O(C * n) faster than O(log n) if n gets sufficiently large.

Пределы Big O не заботятся о постоянных факторах. Если бы алгоритм использовал в среднем n/2 шага или даже всего 0,0001 * n шагов, мы бы все равно записали это как O(n). Конечно, алгоритм O(10 * n) работает медленнее, чем алгоритм O(n), и это абсолютно важно при точной настройке кода, но никакой постоянный коэффициент C не сделает O(C * n) быстрее, чем O(log n), если n станет достаточно большим.

There are better ways to check whether an element is present in some data than searching the list sequentially. We will explore one of them in the next section, Big O and Delphi data structures.

Есть лучшие способы проверить, присутствует ли элемент в некоторых данных, чем последовательный поиск по списку. Мы рассмотрим один из них в следующем разделе, Big O и структуры данных Delphi.

While the function of n inside the O() notation can be anything, there are some O functions that appear constantly in standard programming problems. The following table shows those Big O limits and the most common examples of problems that belong to each class:

В то время как функция n внутри обозначения O() может быть --">