Зарегистрируйтесь, чтобы продолжить обучение

Алгоритмическая сложность Основы алгоритмов и структур данных

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

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

Как оценить скорость алгоритма

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

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 миллисекунд

https://replit.com/@hexlet/js-complexity-qsort#index.js

Python 
from datetime import datetime

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 миллисекунд

https://replit.com/@hexlet/python-complexity-qsort#main.py

PHP 
<?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);
};

$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];
$start = microtime(true);
quickSort($items);
$end = microtime(true);
print_r($end - $start); // => 0.20 миллисекунд

https://replit.com/@hexlet/php-complexity-qsort#main.php

Java 
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 = System.nanoTime();
App.quicksort(items);
var end = System.nanoTime();
System.out.println(end - start); // 0.2 миллисекунд

https://replit.com/@hexlet/java-complexity-qsort#src/main/java/Main.java

Алгоритм быстрой сортировки мы уже разбирали. Единственное, что нам пока не встречалось — вызов метода 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 миллисекунды

https://replit.com/@hexlet/js-complexity-selection#index.js

Python 
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 миллисекунды

https://replit.com/@hexlet/python-complexity-selection#main.py

PHP 
<?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;
    }
}

$items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28];
$start = microtime(true);
selectionSort($items);
$end = microtime(true);
print_r($end - $start); // <= 0.09 миллисекунды

https://replit.com/@hexlet/php-complexity-selection#main.php

Java 
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 = System.nanoTime();
App.selectionSort(items);
var end = System.nanoTime();
System.out.println(end - start); // 0.09 миллисекунд

https://replit.com/@hexlet/java-complexity-selection

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

  • Быстрая сортировка — 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

https://replit.com/@hexlet/js-complexity-average#index.js

Python 
from datetime import datetime

def average_performance(f, args, count):
    start = datetime.now()

    for i in range(count):
        f(*args)

    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

https://replit.com/@hexlet/python-complexity-average#main.py

PHP 
<?php

function averagePerformance($f, $args, $count)
{
    $start = microtime(true);

    for ($i = 0; $i < $count; $i++) {
        $f(...$args);
    }

    $end = microtime(true);
    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

https://replit.com/@hexlet/php-complexity-average#main.php

Java 
public class App {

    public static double averagePerformance (Runnable f, int count) {
        var start = System.nanoTime();

        for (var i = 0; i < count; i++) {
            f.run();
        }

        var end = System.nanoTime();
        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

https://replit.com/@hexlet/java-complexity-average#src/main/java/Main.java

Возможно вы не знакомы с конструкцией […​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

https://replit.com/@hexlet/js-complexity-100#index.js

Python 
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

https://replit.com/@hexlet/python-complexity-100#main.py

PHP 
<?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];

print_r(averagePerformance(fn() => $selectionSort, [...$items], 10)); // 34
print_r(averagePerformance(fn() => $quickSort, [...$items], 10)); // 9.7

https://replit.com/@hexlet/php-complexity-100#main.php

Java 
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

https://replit.com/@hexlet/java-complexity-100#src/main/java/Main.java

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

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

Оценка скорости алгоритмов «в целом»

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

eyJpZCI6IjEwNTRkYWVjMjc2Mzc5YmJhZjAzMDc5MzBiNmFhODU2LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=de62db4abe7f4a668522da8415678db29af6600b81217aee7ff1e89433816362

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

eyJpZCI6IjA0MWU1ZWQ2MGJlZjkzYzY4Mzg4YzZhZGQxYTY5YWYxLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=2b84db99a7eb1af9d69488e9771ad5e43a2dc650f1636095f5d5e50f9054a887

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

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

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

Линейная сложность

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

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

const getMinimum = (items) => {
  let minimum = items[0];

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

  return minimum;
};
Python 
def get_minimum(items):
    minimum = items[0]

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

    return minimum
PHP 
<?php

function getMinimum($items)
{
    $minimum = $items[0];

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

    return $minimum;
};
Java 
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;
    }
}

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

let minimum = items[0];
Python 
minimum = items[0]
PHP 
<?php

$minimum = $items[0];
Java 
var minimum = items[0];

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

for (let i = 1; i < items.length; i++) {
  if (minimum > items[i]) {
    minimum = items[i];
  }
}
Python 
for i in range(1, len(items)):
    if minimum > items[i]:
        minimum = items[i]
PHP 
<?php

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

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

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

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

const average = (items) => {
  let sum = 0;

  for (let i = 0; i < items.length; i++) {
    sum = sum + items[i];
  }

  return sum / items.length;
};
Python 
def get_average(items):
    sum = 0

    for i in range(len(items)):
        sum = sum + items[i]

    return sum / len(items)
PHP 
<?php

function average($items)
{
    $sum = 0;

    for ($i = 0; $i < count($items); $i++) {
        $sum = $sum + $items[$i];
    }

    return $sum / count($items);
}
Java 
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;
    }
}

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

Палиндромом называется строка, которая одинаково читается слева направо и справа налево. АНА и 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
Python 
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 
<?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
Java 
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

В этом алгоритме цикл выполняется раз, где — длина строки. Казалось бы, сложность работы алгоритма должна быть равна . Но, как и в прошлый раз, это не так. Алгоритмы со временем работы , , и — все имеют сложность , и снова это кажется странным.

Квадратичная сложность

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

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

  // …
}
Python 
for i in range(len(items) - 1):
    for j in range(i + 1, len(items):
        # ...
    # ...
PHP 
<?php

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

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

  // …
}

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

Для расчетов мы взяли формулу суммы членов арифметической прогрессии. Среди слагаемых есть , так что речь идет о квадратичной сложности, которая записывается как . И снова встает вопрос: почему мы игнорируем деление на и слагаемое ? Настало время разобраться.

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

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

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

Именно поэтому программисты и математики избавляются от деталей в нотации O-большое. Записи вида , и превращаются в , и соответственно.

Какая еще бывает сложность

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

Константная сложность

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

const sortedMinimum = (sortedItems) => {
  return sortedItems[0];
};
Python 
def sorted_minimum(sorted_items):
    return sorted_items[0]
PHP 
<?php

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

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

Логарифмическая сложность

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

eyJpZCI6IjM1NWZhMWE2MTQyNWQzZmI5ZjU2NzI2YmNhMzY3MTVkLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=98b5920d60a22f16b858ec95fdec6db252c37cba4a4703882ec31ea2a5187e45

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

1000

10

1000

1000000

20

1000000

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

Линейно-логарифмическая сложность

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

Быстрая

Выбор

1000

10000

1000000

1000000

20000000

1000000000000

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

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

Экспоненциальная сложность

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

  • Подмассивы могут быть любой длины, включая ноль

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

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

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

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

Факториальная сложность

Обозначается . Факториалом числа называют произведение , то есть всех чисел от до . Сложность алгоритма, который находит все перестановки массива, равна . Вот все перестановки массива :

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

Сводная таблица временной сложности

Название

Формула

Примеры алгоритмов

Константная

Длина массива

Логарифмическая

Бинарный поиск

Линейная

Поиск методом перебора

Линейно-логарифмическая

Быстрая сортировка

Квадратичная

Сортировка выбором, пузырьковая сортировка

Экспоненциальная

Список подмассивов

Факториальная

Список перестановок

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

Оценка памяти

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

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

Линейная сложность означает, что алгоритм во время работы сохраняет дополнительные данные, размер которых соизмерим с входными данными. Например, если мы хотим избавиться от дубликатов в массиве, мы можем хранить просмотренные элементы в структуре множество (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]);
    }
  }
};
Python 
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 
<?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;
}
Java 
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?

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

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

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

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

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

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

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

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

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

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

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

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

  return true;
};
Python 
def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
Java 
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. Выбрать самый быстрый алгоритм оказывается не так просто. Измерения на конкретных данных не позволяют прогнозировать время и память алгоритмов на других данных

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

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

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

Дополнительные материалы

  1. Сервис, на котором можно сравнить производительность двух фрагментов кода
Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
130
курсов
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»