basics_of_algorithms:algorithmic_complexity []

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

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

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

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

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

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

<details> <summary>Python</summary>

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

</details>

<details> <summary>PHP</summary>

<code 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);
};

// Вспомогательная функция,
// которая возвращает количество микросекунд
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 миллисекунд
</code>

</details>

<details> <summary>Java</summary>

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

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

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

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

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

<details> <summary>Python</summary>

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

</details>

<details> <summary>PHP</summary>

<code 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;
    }
}

// Вспомогательная функция,
// которая возвращает количество микросекунд
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 миллисекунды
</code>

</details>

<details> <summary>Java</summary>

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

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

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

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

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

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

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

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

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

<code javascript>
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
</code>

<details> <summary>Python</summary>

<code python>
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
</code>

</details>

<details> <summary>PHP</summary>

<code php>
<?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
</code>

</details>

<details> <summary>Java</summary>

<code java>
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
</code>

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

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

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

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

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

<code javascript>
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
</code>

<details> <summary>Python</summary>

<code 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
</code>

</details>

<details> <summary>PHP</summary>

<code 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];
averagePerformance(fn() => selectionSort([...$items]), 10); // 183
averagePerformance(fn() => quickSort([...$items]), 10); // 65
</code>

</details>

<details> <summary>Java</summary>

<code 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
</code>

</details>

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

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

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

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

{{  :basics_of_algorithms:image_processing20231003-35-owhrjh.png  }}

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

{{  :basics_of_algorithms:image_processing20231003-26-x31ief.png  }}

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

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

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

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

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

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

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

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

  return minimum;
};
</code>

<details> <summary>Python</summary>

<code python>
def get_minimum(items):
    minimum = items[0]

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

    return minimum
</code>

</details>

<details> <summary>PHP</summary>

<code php>
<?php

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

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

    return $minimum;
};
</code>

</details>

<details> <summary>Java</summary>

<code 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;
    }
}
</code>

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

<code javascript>
let minimum = items[0];
</code>

<details> <summary>Python</summary>

<code python>
minimum = items[0]
</code>

</details>

<details> <summary>PHP</summary>

<code php>
<?php

$minimum = $items[0];
</code>

</details>

<details> <summary>Java</summary>

<code java>
var minimum = items[0];
</code>

</details> Второй элемент — это цикл:

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

<details> <summary>Python</summary>

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

</details>

<details> <summary>PHP</summary>

<code php>
<?php

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

</details>

<details> <summary>Java</summary>

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

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

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

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

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

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

  return sum / items.length;
};
</code>

<details> <summary>Python</summary>

<code python>
def get_average(items):
    sum = 0

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

    return sum / len(items)
</code>

</details>

<details> <summary>PHP</summary>

<code php>
<?php

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

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

    return $sum / count($items);
}
</code>

</details>

<details> <summary>Java</summary>

<code 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;
    }
}
</code>

</details>

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

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

<code javascript>
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
</code>

<details> <summary>Python</summary>

<code 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
</code>

</details>

<details> <summary>PHP</summary>

<code 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
</code>

</details>

<details> <summary>Java</summary>

<code 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
</code>

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

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

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

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

  // …
}
</code>

<details> <summary>Python</summary>

<code python>
for i in range(len(items) - 1):
    for j in range(i + 1, len(items):
        # ...
    # ...
</code>

</details>

<details> <summary>PHP</summary>

<code php>
<?php

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

    // …
}
</code>

</details>

<details> <summary>Java</summary>

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

  // …
}
</code>

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

{{  :basics_of_algorithms:eqweqweqwewq.png  }}

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

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

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

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

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

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

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

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

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

<code javascript>
const sortedMinimum = (sortedItems) => {
  return sortedItems[0];
};
</code>

<details> <summary>Python</summary>

<code python>
def sorted_minimum(sorted_items):
    return sorted_items[0]
</code>

</details>

<details> <summary>PHP</summary>

<code php>
<?php

function sortedMinimum($sortedItems)
{
  return $sortedItems[0];
}
</code>

</details>

<details> <summary>Java</summary>

<code java>
public class App {
    public static int sortedMinimum(int[] sortedItems) {
        return sortedItems[0];
    }
}
</code>

</details>

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

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

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

{{  :basics_of_algorithms:image_processing20231003-35-rqiitr.png  }}

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

|n|O(log*n)|O(n)|
|1000|10|1000|
|1000000|20|1000000|

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

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

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

| |Быстрая O(n*logn)  |Выбор O(n<sup>2</sup> )|
|1000|10000|1000000|
|1000000|20000000|1000000000000|

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

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

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

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

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

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

|<nowiki>[]</nowiki>|<nowiki>[4]</nowiki>|<nowiki>[2,3]</nowiki>|<nowiki>[1,2,4]</nowiki>|
|<nowiki>[1]</nowiki>|<nowiki>[1,2]</nowiki>|<nowiki>[2,4]</nowiki>|<nowiki>[1,3,4]</nowiki>|
|<nowiki>[2]</nowiki>|<nowiki>[1,3]</nowiki>|<nowiki>[3,4]</nowiki>|<nowiki>[2,3,4]</nowiki>|
|<nowiki>[3]</nowiki>|<nowiki>[1,4]</nowiki>|<nowiki>[1,2,3]</nowiki>|<nowiki>[1,2,3,4]</nowiki>|

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

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

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

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

|<nowiki>[1,2,3,4]</nowiki>|<nowiki>[2,1,3,4]</nowiki>|<nowiki>[3,2,1,4]</nowiki>|<nowiki>[4,2,3,1]</nowiki>|
|<nowiki>[1,2,4,3]</nowiki>|<nowiki>[2,1,3,3]</nowiki>|<nowiki>[3,2,4,1]</nowiki>|<nowiki>[4,2,1,3]</nowiki>|
|<nowiki>[1,3,2,4]</nowiki>|<nowiki>[2,3,1,4]</nowiki>|<nowiki>[3,1,2,4]</nowiki>|<nowiki>[4,3,2,1]</nowiki>|
|<nowiki>[1,3,4,2]</nowiki>|<nowiki>[2,3,4,1]</nowiki>|<nowiki>[3,1,4,2]</nowiki>|<nowiki>[4,3,1,2]</nowiki>|
|<nowiki>[1,4,2,3]</nowiki>|<nowiki>[2,4,1,3]</nowiki>|<nowiki>[3,4,2,1]</nowiki>|<nowiki>[4,1,2,3]</nowiki>|
|<nowiki>[1,4,3,2]</nowiki>|<nowiki>[2,4,3,1]</nowiki>|<nowiki>[3,4,1,3]</nowiki>|<nowiki>[4,1,3,2]</nowiki>|

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

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

|**Название** |**Формула** |**Примеры алгоритмов** |
|Константная|o(1)|Длина массива|
|Логарифмическая|O(logn)|Бинарный поиск|
|Линейная|O(n)|Поиск методом перебора|
|Линейно-логарифмическая|O(nlogn)|Быстрая сортировка|
|Квадратичная|O(n<sup>2</sup> )|Сортировка выбором, пузырьковая сортировка|
|Экспоненциальная|O(2<sup>n</sup> )|Список подмассивов|
|Факториальная|O(n!)|Список перестановок|

Иногда в литературе можно встретить название **полиномиальные алгоритмы**  — к ним относят алгоритмы со сложностью O(n<sup>2</sup> ), O(n<sup>3</sup> ) или O(n<sup>100</sup> ). Условная граница между медленными и быстрыми алгоритмами проходит между **полиномиальными**  и **экспоненциальными алгоритмами**.

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

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

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

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

<code javascript>
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]);
    }
  }
};
</code>

<details> <summary>Python</summary>

<code 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
</code>

</details>

<details> <summary>PHP</summary>

<code 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;
}
</code>

</details>

<details> <summary>Java</summary>

<code 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));
            }
        }
    }
</code>

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

===== Оптимизация =====

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

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

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

Определение простых чисел и звучит очень просто — простые числа делятся на себя и на единицу. Но проверить число на простоту уже сложнее — попробуйте, например, выяснить — простое ли число 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|<color /#fff3cd>4</color>|5|<color /#fff3cd>6</color>|
|7|<color /#fff3cd>8</color>|9|<color /#fff3cd>10</color>|11|
|<color /#fff3cd>12</color>|13|<color /#fff3cd>14</color>|15|<color /#fff3cd>16</color>|
|17|<color /#fff3cd>18</color>|19|<color /#fff3cd>20</color>|21|
|<color /#fff3cd>22</color>|23|<color /#fff3cd>24</color>|25|<color /#fff3cd>26</color>|

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

|2|3|<color /#fff3cd>4</color>|5|<color /#fff3cd>6</color>|
|7|<color /#fff3cd>8</color>|<color /#fff3cd>9</color>|<color /#fff3cd>10</color>|11|
|<color /#fff3cd>12</color>|13|<color /#fff3cd>14</color>|<color /#fff3cd>15</color>|<color /#fff3cd>16</color>|
|17|<color /#fff3cd>18</color>|19|<color /#fff3cd>20</color>|<color /#fff3cd>21</color>|
|<color /#fff3cd>22</color>|23|<color /#fff3cd>24</color>|25|<color /#fff3cd>26</color>|

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

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

Сама процедура выделения чисел на каждой итерации пробегает N чисел. Итого, выходит N чисел на итерацию и √N итераций. Сложность алгоритма по времени равна O(N x √N) или в более математической записи — O(N<sup>3/2</sup> ). При этом нам приходится выделять память для всех N чисел, поэтому сложность по памяти равна O(N).

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

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

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

  return true;
};
</code>

<details> <summary>Python</summary>

<code python>
def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
</code>

</details>

<details> <summary>Java</summary>

<code 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;
    }
}
</code>

</details> Этот алгоритм линейный по времени, он работает за O(N). Он константный по памяти, O(1), поскольку количество потребляемой памяти не зависит от N.

Он работает гораздо быстрее Решета, но все еще не самый оптимальный. Как мы помним, для проверки нам не обязательно делить N на все числа меньше себя, достаточно проверить только числа от 2 до √N, так что алгоритм можно переписать.

Алгоритмическая сложность переписанного алгоритма равна O(√N) или O(N<sup>1/2</sup> ).

===== Выводы =====

  - При общих равных условиях программисты выбирают самые быстрые и самые экономичные алгоритмы
  - Выбрать самый быстрый алгоритм оказывается не так просто. Измерения на конкретных данных не позволяют прогнозировать время и память алгоритмов на других данных
  - Программисты используют нотацию О-большое, чтобы оценить производительность алгоритмов в целом
  - Чаще всего встречаются такие сложности, как константная, логарифмическая, линейная, линейно-логарифмическая, квадратическая, экспоненциальная и факториальная. В этом списке они распределены в порядке от самой быстрой к самой медленной
  - Нотация О-большое оценивает не только скорость алгоритма, но и память, которую он использует
===== Примеры ===== 
Реализуйте функцию, которая проверяет являться ли число простым или нет.

Оптимизируйте алгоритм так, чтобы он выполнялся за наименьшее количество итераций

**solutions/solution.js**
Реализуйте и экспортируйте функцию по умолчанию
<code javascript>
import isPrime from './solution.js';

isPrime(2147483648) // false
isPrime(87178291199) // true
</code>

**Решение:**
<code javascript>
const isPrime = (number) => {
  if (number < 2) {
    return false;
  }

  const sqrt = Math.sqrt(number);
  for (let i = 2; i <= sqrt; i += 1) {
    if (number % i === 0) {
      return false;
    }
  }

  return true;
};

export default isPrime;
</code>


<details>
<summary>**solutions/solution.php**</summary>
Реализуйте функцию <color red>solution</color>.
<code php> 
<?php

solution(2147483648) # False
solution(87178291199) # True
</code>
**Решение:**
<code php>
<?php

function solution(int $num): bool
{
    if ($num < 2) {
        return false;
    }

    for ($i = 2; $i <= sqrt($num); $i += 1) {
        if ($num % $i == 0) {
            return false;
        }
    }

    return true;
}
</code>
</details>



<details>

<summary>**solutions/solution.py**</summary>
Реализуйте функцию solution.
<code python>
from solution import solution

solution(2147483648) # False
solution(87178291199) # True
</code>
**Решение:**
<code python>
import math


def solution(number):
    if number < 2:
        return False

    sqrt = math.sqrt(number)
    for i in range(2, int(sqrt)):
        if number % i == 0:
            return False

    return True
</code>
</details>


<details>
<summary>**solutions/Solution.java**</summary>
В файле определите пакет <color red>solutions</color>. Создайте в нем публичный класс Solution и реализуйте в нем публичный статический метод <color red>run()</color>. Метод принимает в качестве параметра целое число типа <color red>long</color> и проверяет, является ли оно простым или нет
<code java>
Solution.run(2147483648); // false
Solution.run(87178291199); // true
</code>
Оптимизируйте алгоритм так, чтобы он выполнялся за наименьшее количество итераций
**Решение:**
<code java>
package solutions;

public class Solution {
    public static boolean run(long number) {
        if (number < 2) {
            return false;
        }

        var sqrt = Math.sqrt(number);

        for (var i = 2; i <= sqrt; i++) {
            if (number % i == 0) {
                return false;
            }
        }

        return true;
    }
}
</code>
</details>
Инструменты пользователя

Инструменты сайта

Инструменты страницы
