В программировании используются алгоритмы, которые по-разному решают одну и ту же задачу: например, сортировку массива. При этом алгоритмы работают с разной скоростью и требуют разное количество памяти. При прочих равных условиях мы бы выбрали быстрый или нетребовательный алгоритм.

Чтобы правильно выбирать алгоритмы, нужно научиться сравнивать их, чем мы и займемся в этом уроке. Мы познакомимся с двумя основными способами, разберем их плюсы и минусы. Опираясь на эти способы, мы сравним время работы уже знакомых нам алгоритмов.

Скорость алгоритмов можно сравнивать самым очевидным способом — физически измерить время выполнения на одних и тех же данных. Чтобы сравнить сортировку выбором и быструю сортировку, мы можем взять массив из нескольких элементов и измерить время быстрой сортировки:

const quickSort = (items) => {
  const partition = (items, left, right, pivot) => {
    while (true) {
      while (items[left] < pivot) {
        left++;
      }
 
      while (items[right] > pivot) {
        right--;
      }
 
      if (left >= right) {
        return right + 1;
      }
 
      const t = items[left];
      items[left] = items[right];
      items[right] = t;
 
      left++;
      right--;
    }
  };
 
  const quickSort = (items, left, right) => {
    const length = right - left + 1;
    if (length < 2) {
      return;
    }
 
    const pivot = items[left];
 
    const split_index = partition(items, left, right, pivot);
 
    quickSort(items, left, split_index - 1);
    quickSort(items, split_index, right);
  };
 
  quickSort(items, 0, items.length - 1);
};
 
 
const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];
const start = performance.now();
quickSort(items);
const end = performance.now();
console.log(end - start); // <= 0.20 миллисекунд

def quick_sort(items):
    def partition(items, left, right, pivot):
        while True:
            while items[left] < pivot:
                left += 1
 
            while items[right] > pivot:
                right -= 1
 
            if left >= right:
              return right + 1
 
            items[left], items[right] = items[right], items[left]
            left += 1
            right -= 1
 
    def quick_sort(items, left, right):
        length = right - left + 1
 
        if length < 2:
            return
 
        pivot = items[left]
        split_index = partition(items, left, right, pivot)
        quick_sort(items, left, split_index - 1)
        quick_sort(items, split_index, right)
 
    quick_sort(items, 0, len(items) - 1)
 
items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];
start = datetime.now();
quick_sort(items);
end = datetime.now();
print(end - start); # <= 0.20 миллисекунд

<?php
 
function quickSort($items)
{
    $partition = function ($items, $left, $right, $pivot) {
        while (true) {
            while ($items[$left] < $pivot) {
                $left += 1;
            }
 
            while ($items[$right] > $pivot) {
                $right -= 1;
            }
 
            if ($left >= $right) {
                return $right + 1;
            }
 
            $t = $items[$left];
            $items[$left] = $items[$right];
            $items[$right] = $t;
 
            $left += 1;
            $right -= 1;
        }
    };
 
    $quickSort = function ($items, $left, $right) use ($partition, &$quickSort) {
        $length = $right - $left + 1;
        if ($length < 2) {
            return;
        }
 
        $pivot = $items[$left];
 
        $splitIndex = $partition($items, $left, $right, $pivot);
 
        $quickSort($items, $left, $splitIndex - 1);
        $quickSort($items, $splitIndex, $right);
    };
 
    $quickSort($items, 0, count($items) - 1);
};
 
// Вспомогательная функция,
// которая возвращает количество микросекунд
function microseconds() {
    $mt = explode(' ', microtime());
    [$msec, $sec] = $mt;
    return (int)$sec * 1000000 + ((int) round($msec * 1000000));
}
 
$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];
$start = microseconds();
quickSort($items);
$end = microseconds();
print_r($end - $start); // <= 0.20 миллисекунд

class App {
    public static int partition(int[] items, int left, int right, int pivot) {
        while (true) {
            while (items[left] < pivot) {
                left++;
            }
 
            while (items[right] > pivot) {
                right--;
            }
 
            if (left >= right) {
                return right + 1;
            }
 
            var temporary = items[left];
            items[left] = items[right];
            items[right] = temporary;
 
            left++;
            right--;
        }
    }
 
    public static void sort(int[] items, int left, int right) {
        var length = right - left + 1;
 
        if (length < 2) {
            return;
        }
 
        var pivot = items[left];
 
        var splitIndex = partition(items, left, right, pivot);
        sort(items, left, splitIndex - 1);
        sort(items, splitIndex, right);
    }
 
    public static void quicksort(int[] items) {
        sort(items, 0, items.length - 1);
    }
}
 
int[] items = {86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28};
 
var start = Instant.now().toEpochMilli();
App.quicksort(items);
var end = Instant.now().toEpochMilli();
System.out.println(end - start); // 0.2 миллисекунд

Алгоритм быстрой сортировки мы уже разбирали. Единственное, что нам пока не встречалось — вызов метода performance.now().

Performance — это объект в глобальной области видимости, который используют для измерения производительности. Метод now() возвращает количество миллисекунд с момента старта браузера. Можно запустить этот метод, сохранить значения до запуска кода и после его завершения, и вычесть одно из другого — и тогда мы узнаем, сколько миллисекунд работал наш код.

Чтобы сравнить два алгоритма, надо упорядочить точно такой же массив с помощью алгоритма выбора:

const selectionSort = (items) => {
  for (i = 0; i < items.length - 1; i++) {
    let indexMin = i;
    for (j = i + 1; j < items.length; j++) {
      if (items[j] < items[indexMin])
        indexMin = j;
    }
 
    const t = items[i];
    items[i] = items[indexMin];
    items[indexMin] = t;
  }
};
 
const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];
const start = performance.now();
selectionSort(items);
const end = performance.now();
console.log(end - start); // <= 0.09 миллисекунды

from datetime import datetime
 
def selection_sort(items):
    for i in range(len(items) - 1):
        index_min = i
        for j in range(i + 1, len(items) - 1):
              if items[j] < items[index_min]:
                  index_min = j
        items[i], items[index_min] = items[index_min], items[i]
 
items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]
start = datetime.now()
selection_sort(items)
end = datetime.now()
print(end - start) # <= 0.09 миллисекунды

<?php
 
function selectionSort($items)
{
    for ($i = 0; $i < count($items) - 1; $i++) {
        $indexMin = $i;
        for ($j = $i + 1; $j < count($items); $j++) {
            if ($items[$j] < $items[$indexMin]) {
                $indexMin = $j;
            }
        }
 
        $t = $items[$i];
        $items[$i] = $items[$indexMin];
        $items[$indexMin] = $t;
    }
}
 
// Вспомогательная функция,
// которая возвращает количество микросекунд
function microseconds() {
    $mt = explode(' ', microtime());
    [$msec, $sec] = $mt;
    return (int)$sec * 1000000 + ((int) round($msec * 1000000));
}
 
$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];
$start = performance.now();
selectionSort($items);
$end = performance.now();
print_r($end - $start); // <= 0.09 миллисекунды

class App {
    public static void selectionSort(int[] items) {
        for (var i = 0; i < items.length - 1; i++) {
            var indexMin = i;
            for (var j = i + 1; j < items.length; j++) {
                if (items[j] < items[indexMin]) {
                    indexMin = j;
                }
            }
 
            var temporary = items[i];
            items[i] = items[indexMin];
            items[indexMin] = temporary;
        }
    }
}
 
int[] items = {86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28};
 
var start = Instant.now().toEpochMilli();
App.selectionSort(items);
var end = Instant.now().toEpochMilli();
System.out.println(end - start); // 0.09 миллисекунд

Оценим скорость кода выше:

• Быстрая сортировка — 0,20 миллисекунд
• Сортировка выбором — 0,09 миллисекунд

Результат выглядит странно. Раз уж быструю сортировку назвали быстрой, то время ее выполнения должно быть меньше, чем у сортировки выбором. Здесь дело в том, что результаты однократного измерения ненадежны. Нужно измерить производительность алгоритмов несколько раз подряд на одних и тех же данных. Можем получить такой результат:

• Быстрая сортировка — 0,21 миллисекунда
• Сортировка выбором — 0,12 миллисекунд

Или даже такой:

• Быстрая сортировка — 0,16 миллисекунд
• Сортировка выбором — 0,17 миллисекунд

Разброс может быть достаточно большим. Дело в том, что на производительность нашей программы влияет множество случайных факторов: другие запущенные программы на компьютере, режим энергосбережения и так далее.

В работе алгоритмов много перечисленных тонкостей, поэтому сравнивать скорости довольно трудно. Чтобы справиться с этой трудностью, используем статистические методы. Будем запускать одну и ту же функцию много раз, а затем разделим общее время выполнения на количество запусков, чтобы вычислить среднее время выполнения:

const averagePerformance = (f, count) => {
  const start = window.performance.now();
 
  for (let i = 0; i < count; i++) {
    f();
  }
 
  const end = window.performance.now();
  return (end - start) / count;
};
 
const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];
averagePerformance(() => selectionSort([...items]), 1); // 0.1000000238418
averagePerformance(() => selectionSort([...items]), 10); // 0.0699999988079

from datetime import datetime
 
def average_performance(f, count):
    start = datetime.now()
 
    for i in range(count):
        f()
 
    end = datetime.now()
 
    return (end - start) / count
 
items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]
average_performance(selection_sort(items[:]), 1) # 0.1000000238418
average_performance(selection_sort(items[:]), 10) # 0.0699999988079

<?php
 
// Вспомогательная функция,
// которая возвращает количество микросекунд
function microseconds() {
    $mt = explode(' ', microtime());
    [$msec, $sec] = $mt;
    return (int)$sec * 1000000 + ((int) round($msec * 1000000));
}
 
function averagePerformance($f, $count)
{
    $start = microseconds();
 
    for ($i = 0; $i < $count; $i++) {
        $f();
    }
 
    $end = microseconds();
    return ($end - $start) / $count;
}
 
$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];
averagePerformance(fn() => selectionSort([...$items]), 1); // 34
averagePerformance(fn() => selectionSort([...$items]), 10); // 9.7

public class App {
 
    public static double averagePerformance (Runnable f, int count) {
        var start = Instant.now().toEpochMilli();
 
        for (var i = 0; i < count; i++) {
            f.run();
        }
 
        var end = Instant.now().toEpochMilli();
        System.out.println((end - start) / count);
        return (end - start) / count;
    }
}
 
int[] items = {86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28};
 
App.averagePerformance(() -> selectionSort(Arrays.copyOf(items, items.length)), 1); // 0.1
App.averagePerformance(() -> selectionSort(Arrays.copyOf(items, items.length)), 10);// 0.069

Возможно вы не знакомы с конструкцией […items], которая встречается в этом коде. Она позволяет сделать копию массива items. Без копии мы при первом же вызове функции selectionSort упорядочим массив items, и последующие вызовы будут измерять скорость сортировки уже упорядоченного массива.

У функции averagePerformance два параметра:

• Функция, чью производительность мы хотим измерить
• Количество раз, когда мы хотим ее запустить

Мы видим, что среднее время выполнения может заметно отличаться от времени, измеренного один раз — на 30% в нашем случае. Значит ли это, что теперь у нас в руках есть надежный способ сравнения алгоритмов? Кажется, что да. Но мы пока так и не выяснили, почему быстрая сортировка такая медленная по сравнению с сортировкой выбором.

Продолжим искать причину и сравним время выполнения разных сортировок на массиве из ста элементов:

const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28, 91, 81, 97, 24, 96, 33, 11, 47, 18, 44, 95, 34, 52, 65, 18, 5, 30, 54, 67, 24, 13, 70, 62, 88, 18, 78, 72, 40, 10, 73, 27, 44, 46, 8, 1, 49, 45, 98, 91, 70, 30, 48, 44, 52, 24, 39, 91, 22, 93, 30, 2, 85, 30, 34, 7, 82, 18, 87, 91, 37, 11, 93, 74, 27, 15, 44, 81, 15, 74, 17, 53, 3, 67, 84, 78, 98, 6, 8, 90, 50];
averagePerformance(() => selectionSort([...items]), 10); // 0.60
averagePerformance(() => quickSort([...items]), 10); // 0.19

items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28, 91, 81, 97, 24, 96, 33, 11, 47, 18, 44, 95, 34, 52, 65, 18, 5, 30, 54, 67, 24, 13, 70, 62, 88, 18, 78, 72, 40, 10, 73, 27, 44, 46, 8, 1, 49, 45, 98, 91, 70, 30, 48, 44, 52, 24, 39, 91, 22, 93, 30, 2, 85, 30, 34, 7, 82, 18, 87, 91, 37, 11, 93, 74, 27, 15, 44, 81, 15, 74, 17, 53, 3, 67, 84, 78, 98, 6, 8, 90, 50]
average_performance(selection_sort(items[:]), 10) # 0.60
average_performance(quick_sort(items[:]), 10) # 0.19

<?php
 
$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28, 91, 81, 97, 24, 96, 33, 11, 47, 18, 44, 95, 34, 52, 65, 18, 5, 30, 54, 67, 24, 13, 70, 62, 88, 18, 78, 72, 40, 10, 73, 27, 44, 46, 8, 1, 49, 45, 98, 91, 70, 30, 48, 44, 52, 24, 39, 91, 22, 93, 30, 2, 85, 30, 34, 7, 82, 18, 87, 91, 37, 11, 93, 74, 27, 15, 44, 81, 15, 74, 17, 53, 3, 67, 84, 78, 98, 6, 8, 90, 50];
averagePerformance(fn() => selectionSort([...$items]), 10); // 183
averagePerformance(fn() => quickSort([...$items]), 10); // 65

int[] items = {6, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28, 91, 81, 97, 24, 96, 33, 11, 47, 18, 44, 95, 34, 52, 65, 18, 5, 30, 54, 67, 24, 13, 70, 62, 88, 18, 78, 72, 40, 10, 73, 27, 44, 46, 8, 1, 49, 45, 98, 91, 70, 30, 48, 44, 52, 24, 39, 91, 22, 93, 30, 2, 85, 30, 34, 7, 82, 18, 87, 91, 37, 11, 93, 74, 27, 15, 44, 81, 15, 74, 17, 53, 3, 67, 84, 78, 98, 6, 8, 90, 50};
 
App.averagePerformance(() -> selectionSort(Arrays.copyOf(items, items.length)), 10); // 0.6
App.averagePerformance(() -> quickSort(Arrays.copyOf(items, items.length)), 10);// 0.19

На большом массиве быстрая сортировка оказывается в три раза быстрее, чем сортировка выбором! Как такое может быть? Конечно, у этой странности есть объяснение, мы обсудим его чуть позже. Сейчас обратим внимание, что измерения скорости алгоритма на одних данных ничего не говорит об его скорости на других данных.

Мы можем с большой точностью оценить время работы алгоритма на массиве из десяти элементов и при этом мы совершенно не представляем, какой окажется скорость того же алгоритма на массиве из ста тысяч элементов. Именно поэтому перед программистами встала задача — научиться оценивать скорость алгоритмов в целом.

Идея оценки «в целом» пришла к нам из математики, где есть похожая задача — нужно оценивать порядок роста функций. Математики могут точно рассчитать скорость возрастания функции в любой точке, но эта информация может оказаться не очень полезной. Сравним графики двух функций:

Кажется, что синяя функция больше, чем, красная. Но если посмотреть на те же графики в другом масштабе, картина изменится:

Красная функция растет гораздо быстрее и почти сразу становится больше синей. С алгоритмами возникает та же проблема: на одном наборе данных первый алгоритм физически будет быстрее второго, на многих других наборах он может оказаться гораздо медленнее. Синяя функция на графике — это прямая линия, а красная — это парабола.

Синие функции в математике принято называть линейными, а красные — квадратичными. Математики знают, что квадратичные функции растут быстрее линейных, а кубические — быстрее квадратичных.

Алгоритмическая сложность тоже бывает линейной, квадратичной и кубической. Для нее характерна та же самая зависимость: алгоритмы с квадратичной сложностью в целом работают медленнее алгоритмов с линейной сложностью. Рассмотрим несколько алгоритмов и разберемся, как определять временную сложность.

Чтобы определить временную сложность алгоритма, программисты ставят мысленный эксперимент. Предположим, что мы точно измерили время работы алгоритма на одном массиве, а потом увеличили этот массив в десять раз. Как увеличится время работы алгоритма? Если время работы алгоритма также увеличится в десять раз, то речь идет о линейной сложности — на графике она бы описывалась прямой линией.

Типичный линейный алгоритм — поиск минимального элемента в массиве:

const getMinimum = (items) => {
  let minimum = items[0];
 
  for (let i = 1; i < items.length; i++) {
    if (minimum > items[i]) {
      minimum = items[i];
    }
  }
 
  return minimum;
};

def get_minimum(items):
    minimum = items[0]
 
    for i in range(1, len(items)):
        if minimum > items[i]:
            minimum = items[i]
 
    return minimum

<?php
 
function getMinimum($items)
{
    $minimum = $items[0];
 
    for ($i = 1; i < count($items); $i++) {
        if ($minimum > $items[i]) {
            $minimum = $items[i];
        }
    }
 
    return $minimum;
};

public class App {
    public static int getMinimum(int[] items) {
        var minimum = items[0];
 
        for (var i = 1; i < items.length; i++) {
            if (minimum > items[i]) {
                minimum = items[i];
            }
        }
 
        return minimum;
    }
}

Это простой алгоритм. Мы просматриваем элементы массива по одному и сравниваем с уже найденным. Если новый элемент оказывается меньше минимума, он становится новым минимумом. В самом начале в качестве минимума выбираем самый первый элемент массива с индексом 0. Функция состоит из двух смысловых элементов. Первый элемент — инициализация:

let minimum = items[0];

minimum = items[0]

<?php
 
$minimum = $items[0];

var minimum = items[0];

Второй элемент — это цикл:

for (let i = 1; i < items.length; i++) {
  if (minimum > items[i]) {
    minimum = items[i];
  }
}

for i in range(1, len(items)):
    if minimum > items[i]:
        minimum = items[i]

<?php
 
for ($i = 1; $i < count($items); $i++) {
  if ($minimum > $items[$i]) {
    $minimum = $items[$i];
  }
}

for (var i = 1; i < items.length; i++) {
    if (minimum > items[i]) {
        minimum = items[i];
    }
}

Если в массиве 10 элементов, цикл выполнится 9 раз, если 100 элементов — 99 раз, если n элементов, цикл выполнится n-1 раз. В итоге, для массива из n элементов функция выполнит n операций — одну операцию инициализации и n-1 операций в цикле. Если увеличить размер массива в 10 раз, то количество элементов будет равно 10*n, и количество операций также будет равно 10*n, то есть тоже вырастет в 10 раз.

Такая линейная временная сложность обозначается O(n). Из-за того, что в записи используется большая буква O, она называется «нотация О-большое». Буква O появилась здесь не случайно. Это первая буква немецкого слова Ordnung, которое означает порядок. В математике, откуда пришло обозначение, оно относится к порядку роста функций.

Какие еще алгоритмы имеют линейную временную сложность? Например, алгоритм вычисления среднего арифметического:

const average = (items) => {
  let sum = 0;
 
  for (let i = 0; i < items.length; i++) {
    sum = sum + items[i];
  }
 
  return sum / items.length;
};

def get_average(items):
    sum = 0
 
    for i in range(len(items)):
        sum = sum + items[i]
 
    return sum / len(items)

<?php
 
function average($items)
{
    $sum = 0;
 
    for ($i = 0; $i < count($items); $i++) {
        $sum = $sum + $items[$i];
    }
 
    return $sum / count($items);
}

public class App {
    public static double average(int[] items) {
        double sum = 0;
 
        for (var i = 0; i < items.length; i++) {
            sum = sum + items[i];
        }
 
        return sum / items.length;
    }
}

Анализ алгоритма показывает, что для массива из элементов будет n+1 операция: одна инициализация плюс n операций в цикле. Кажется, что такая временная сложность должна записываться O(n+1). Однако такие варианты, как n-2, n+5 и даже n+1000, всегда записывают как O(n). На первый взгляд это кажется странным, но далее мы разберемся, почему это так. А пока рассмотрим еще один линейный алгоритм — алгоритм определения строк-палиндромов.

Палиндромом называется строка, которая одинаково читается слева направо и справа налево. АНА и ABBA — это палиндромы, а YES и NO — нет:

const palindrome = (string) => {
  for (let i = 0; i < string.length / 2; i++) {
    if (string[i] != string[string.length - 1 - i]) {
      return false;
    }
  }
 
  return true;
};
 
palindrome('') // true
palindrome('a') // true
palindrome('ab') // false
palindrome('aha') // true
palindrome('abba') // true

def palindrome(string):
    for i in range(len(string) // 2):
        if string[i] != string[len(string) - 1 - i]:
            return False
    return True
 
palindrome('') // true
palindrome('a') // true
palindrome('ab') // false
palindrome('aha') // true
palindrome('abba') // true

<?php
 
function palindrome($string) => {
    for ($i = 0; $i < strlen($string) / 2; i++) {
        if ($string[$i] != $string[strlen($string) - 1 - $i]) {
            return false;
        }
    }
 
    return true;
}
 
palindrome('') // true
palindrome('a') // true
palindrome('ab') // false
palindrome('aha') // true
palindrome('abba') // true

public class App {
    public static boolean palindrome(String word) {
        for (var i = 0; i < word.length() / 2; i++) {
            if (word.charAt(i) != word.charAt(word.length() - 1 - i)) {
                return false;
            }
        }
 
        return true;
    }
}
 
App.palindrome("") // true
App.palindrome("a") // true
App.palindrome("ab") // false
App.palindrome("aha") // true
App.palindrome("abba") // true

В этом алгоритме цикл выполняется n/2 раз, где n — длина строки. Казалось бы, сложность работы алгоритма должна быть равна O(n/2). Но, как и в прошлый раз, это не так. Алгоритмы со временем работы 2n, 10n, n/5 и n/32 — все имеют сложность O(n), и снова это кажется странным.

Квадратичную сложность имеют все простые алгоритмы сортировки. Рассмотрим, например, сортировку выбором. Внутри нее есть вложенный цикл.

for (i = 0; i < items.length - 1; i++) {
  for (j = i + 1; j < items.length; j++) {
    // …
  }
 
  // …
}

for i in range(len(items) - 1):
    for j in range(i + 1, len(items):
        # ...
    # ...

<?php
 
for ($i = 0; $i < count($items) - 1; $i++) {
    for ($j = $i + 1; $j < count($items); $j++) {
        // …
    }
 
    // …
}

for (var i = 0; i < items.length - 1; i++) {
  for (var j = i + 1; j < items.length; j++) {
    // …
  }
 
  // …
}

Чтобы избавиться от несущественных деталей, в коде выше убрана часть операций — вместо них пустые комментарии. Попробуем оценить количество выполнений цикла. На первом шаге внешнего цикла внутренний выполнится n-1 раз, на втором n-2 раз, на третьем n-3 и так далее:

Для расчетов мы взяли формулу суммы членов арифметической прогрессии. Среди слагаемых есть n², так что речь идет о квадратичной сложности, которая записывается как O(n²). И снова встает вопрос: почему мы игнорируем деление на 2 и слагаемое -3n+2? Настало время разобраться.

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

К сожалению, сравнивая два линейных алгоритма, мы не можем сказать, какой из них быстрее. Есть соблазн использовать запись вида O(4n+1) или O(2n-3), но она толкает нас на путь ложных выводов. Определяя алгоритмическую сложность, мы считаем количество операций и предполагаем, что все они выполняются за небольшое постоянное время.

Но как только речь заходит о конкретике, выясняется, что операция сложения может быть очень быстрой, а операция деления — очень медленной по сравнению со сложением. Иногда четыре сложения могут выполниться быстрее, чем два деления. Поэтому нельзя в общем случае утверждать, что O(2n-3) быстрее, чем O(4n+1).

Именно поэтому программисты и математики избавляются от деталей в нотации O-большое. Записи вида O(2n-3), O(n²/3 + 5) и O(20n⁴-1000) превращаются в O(n), O(n²) и O(n⁴) соответственно.

Теоретически мы можем придумать алгоритмы с любой экзотической сложностью, но на практике чаще встречается всего несколько вариантов.

Она обозначается O(1). Алгоритмы с константной временной сложностью выполняются за одно и то же время вне зависимости от количества элементов. Например, в упорядоченном массиве минимальный элемент всегда находится в самом начале, поэтому поиск минимума становится тривиальным:

const sortedMinimum = (sortedItems) => {
  return sortedItems[0];
};

def sorted_minimum(sorted_items):
    return sorted_items[0]

<?php
 
function sortedMinimum($sortedItems)
{
  return $sortedItems[0];
}

public class App {
    public static int sortedMinimum(int[] sortedItems) {
        return sortedItems[0];
    }
}

Эта функция всегда выполняется за одно и то же время, независимо от размера массива sortedItems. Формально, константные алгоритмы считаются самыми быстрыми.

Обозначается . За логарифмическое время работает алгоритм бинарного поиска. Эти алгоритмы относятся к быстрым, поскольку логарифмическая функция растет достаточно медленно.

В массиве из тысячи элементов бинарный поиск работает максимум за десять сравнений, а массиве из миллиона — максимум за двадцать. Обычный метод перебора имеет линейную сложность, и поэтому будет работать за тысячу и миллион сравнений соответственно:

Логарифмические алгоритмы считаются очень быстрыми, гораздо быстрее линейных.

Она обозначается как O(nlogn) и описывает сложность алгоритма быстрой сортировки. Сравним количество операций у быстрой сортировки и сортировки выбором — так мы увидим, почему быстрая сортировка так называется:

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

Линейно-логарифмическая сложность медленнее линейной, но быстрее квадратичной.

Сколько подмассивов можно получить из массива ? Попробуем выяснить, но сначала определимся с условиями:

• Подмассивы могут быть любой длины, включая ноль
• Будем считать одним подмассивом все подмассивы, состоящие из одних и тех же элементов в разном порядке (например, и )

Выпишем все варианты и посчитаем их:

Всего 16. Существует общее правило, по которому возможное количество подмассивов у массива длины n составляет 2ⁿ. Формулы вида 2ⁿ, 3ⁿ, 100ⁿ называют экспонентами. Алгоритм, который может построить список всех подмассивов массива длины n, имеет экспоненциальную сложность O(2ⁿ).

Алгоритмы экспоненциальной сложности считаются медленными. Количество подмассивов у массива из тридцати элементов равно 1073741824, то есть превышает миллиард!

Обозначается O(n!). Факториалом числа называют произведение 1x2x…xX1, то есть всех чисел от 1 до n. Сложность алгоритма, который находит все перестановки массива, равна O(n!). Вот все перестановки массива [1,2,3,4]:

Всего их 4!=24. Факториальная сложность самая медленная из тех, что мы рассмотрели. Если нам потребуется найти все перестановки массива из тридцати элементов, их окажется 265252859812191058636308480000000, то есть 268 миллионов миллионов миллионов миллионов миллионов. Даже на самом быстром современном компьютере поиск всех перестановок займет миллионы миллионов лет.

Иногда в литературе можно встретить название полиномиальные алгоритмы — к ним относят алгоритмы со сложностью O(n²), O(n³) или O(n¹⁰⁰). Условная граница между медленными и быстрыми алгоритмами проходит между полиномиальными и экспоненциальными алгоритмами.

В нотации О-большое также оценивается память, которую потребляет алгоритм. На практике здесь редко встречаются большие значения.

Если алгоритму для работы нужно несколько переменных, которые не зависят от размеров данных, сложность по памяти составляет O(1). Такую сложность имеют алгоритмы поиска минимума и вычисления среднего арифметического. Логарифмическая сложность O(logn) встречается у рекурсивных алгоритмов, которые разбивают массив на два подмассива. Среди рассмотренных нами алгоритмов к этому классу относятся бинарный поиск и быстрая сортировка.

Линейная сложность O(n) означает, что алгоритм во время работы сохраняет дополнительные данные, размер которых соизмерим с входными данными. Например, если мы хотим избавиться от дубликатов в массиве, мы можем хранить просмотренные элементы в структуре множество (Set):

const removeDuplicates = (items) => {
  const visited = new Set();
  for (let i = 0; i < items.length; i++) {
    if (visited.has(items[i])) {
      items.splice(i, 1);
      i--;
    } else {
      visited.add(items[i]);
    }
  }
};

def remove_duplicates(items):
    visited = set()
    i = 0
    while i < len(items):
        if items[i] in visited:
            items.pop(i)
            i -= 1
        else:
            visited.add(items[i])
        i += 1

<?php
 
function removeDuplicates($items)
{
    $visited = new \DS\Set();
    for ($i = 0; $i < count($items); $i++) {
        if ($visited->contains($items[$i])) {
            array_splice($items, $i, 1);
            $i--;
        } else {
            $visited->add($items[$i]);
        }
    }
 
    return $items;
}

public static void removeDuplicates(List<Integer> items) {
        Set<Integer> visited = new HashSet<>();
 
        for (var i = 0; i < items.size(); i++) {
            if(visited.contains(items.get(i))) {
                items.remove(i);
                i--;
            } else {
                visited.add(items.get(i));
            }
        }
    }

Этих неповторяющихся элементов будет чуть меньше, чем элементов в исходном массиве. Но при этом размер множества будет соизмерим с размером массива, поэтому речь идет о линейной сложности по памяти.

Одна из задач, которую регулярно решают программисты — оптимизация программы. Пользователи хотят, чтобы программа работала быстрее или занимала меньше памяти.

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

Разберем пример с определением простоты числа. Простые числа имеют важное значение в криптографии и кодировании, так что программистам время от времени нужен список простых чисел или функция, которая определяет, является ли число простым.

Определение простых чисел и звучит очень просто — простые числа делятся на себя и на единицу. Но проверить число на простоту уже сложнее — попробуйте, например, выяснить — простое ли число 1073676287?

Для определения простоты числа можно использовать один из самых древних, известных человечеству, алгоритмов — Решето Эратосфена. Сначала мы записываем список чисел, начиная с двойки:

Берем первое число — двойку. Выделяем цветом числа, которые делятся на нее. Саму двойку не выделяем:

Следующее неотмеченное число — три. Выделяем цветом числа, которые делятся на три, но не саму тройку:

Четверка зачеркнута — она делится на два, поэтому мы ее пропускаем.

Переходим к пятерке. У нас уже отмечены числа 10, 20 (оба делятся на два) и 15 (делится на три). Единственное неотмеченное число — это 25. Это подсказка, которая помогает понять одну важную мысль — чтобы составить список простых чисел вплоть до , достаточно повторить эту процедуру только для чисел от до .

Сама процедура выделения чисел на каждой итерации пробегает чисел. Итого, выходит чисел на итерацию и итераций. Сложность алгоритма по времени равна или в более математической записи — . При этом нам приходится выделять память для всех чисел, поэтому сложность по памяти равна .

Решето Эратосфена — сложный алгоритм, как по времени, так и по памяти.

Чтобы оптимизировать решение, мы должны найти или придумать другой алгоритм. Обратим внимание, что Решето строит список простых чисел от до , но нам нужно только последнее число . Мы можем проверить, что число не делится ни на какие целые числа от до :

const isPrime = (n) => {
  for (let i = 2; i < n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
 
  return true;
};

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

public class App {
    public static boolean isPrime(int n) {
        for (var i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
 
        return true;
    }
}

1. При общих равных условиях программисты выбирают самые быстрые и самые экономичные алгоритмы
2. Выбрать самый быстрый алгоритм оказывается не так просто. Измерения на конкретных данных не позволяют прогнозировать время и память алгоритмов на других данных