«О» большое: объяснение для тех, у кого нет диплома по информатике

Перевод статьи «Big-O For The Non-CS Degree».

Вам когда-нибудь было любопытно, почему одни алгоритмы работают быстрее других? Да, я раньше тоже как-то не задумывался над этим, а зря. Объяснить это различие в скорости помогает «О» большое.

Что такое это ваше «О» большое?

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

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

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

«О» большое бывает разным:

• O(1)
• O(log n)
• O(n)
• O(n log n)
• O(n^2)
• O(2^n)
• O(n!)

Давайте рассмотрим каждый из вариантов.

O(1) — постоянное время

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

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

let smallList = [0, 1, 2]

let largeList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

let logSecondNumber = (list) => {
    console.log(list[1]);
}

logSecondNumber(smallList)
logSecondNumber(largeList)

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

O(log n) — логарифмическое время

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

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

function binarySearch(array, targetValue) {
    let minIndex = 0;
    let maxIndex = array.length - 1;
    let middleIndex = Math.floor((maxIndex + minIndex) / 2);

    while (array[middleIndex] != targetValue && minIndex < maxIndex) {

        if (targetValue < array[middleIndex]) {
            maxIndex = middleIndex - 1;
        } else if (targetValue > array[middleIndex]) {
            minIndex = middleIndex + 1;
        } 
        middleIndex = Math.floor((maxIndex + minIndex)/2);

    }

    return (array[middleIndex] != targetValue) ? -1 : middleIndex;
};

let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

binarySearch(numbers, 7);

O(n) — линейное время

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

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

let junkFood = ['pizza', 'cookie', 'candy', 'icecream']

loopThroughOurJunkFood(junkFood) {
    for (let i = 0; i > junkFood.length; i++) {
    console.log(junkFood[i]);
    }
}

Если бы мы добавили еще один элемент в массив junkFood, время работы функции возросло бы пропорционально.

O(n log n) — линейно-логарифмическое время

Если временная сложность алгоритма описывается линейно-логарифмической функцией, то, как вы можете догадаться, она занимает промежуточное положение между линейной и логарифмической сложностью. В таком алгоритме тоже применяется подход «разделяй и властвуй», как в алгоритмах с логарифмической сложностью. Но здесь набор данных сначала разбивается на подсписки, состоящие максимум из двух элементов (т. е., на пары).

В нашем примере мы взяли список из 20 элементов. Эти элементы сначала будут разбиты попарно, на 10 подсписков. И здесь вступает в игру «линейная» часть функции. Когда все элементы разбиты попарно, мы сортируем каждую отдельную пару, а затем последовательно объединяем отсортированные пары, продолжая сортировать получившийся результат. Пример алгоритма с линейно-логарифмической временной сложностью — сортировка слиянием.

function merge(left, right) {
    let arr = [];

    while (left.length && right.length) {
        if (left[0] < right[0]) {
            arr.push(left.shift());
        } else {
            arr.push(right.shift());
        }
    }
    return arr.concat(left.slice().concat(right.slice()));
}

function mergeSort(arrayToSort) {
    if (arrayToSort.length < 2) {
        return arrayToSort;
    }

    let middle = Math.floor(arrayToSort.length / 2);
    let left = arrayToSort.slice(0, middle);
    let right = arrayToSort.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

const array = [10, 15, 2, 5, 17, 9, 14, 11, 6, 19, 4, 20, 1, 18, 3, 7, 13, 8, 12, 16];

mergeSort(array.slice());

O(n^2) — квадратичное время

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

Если, к примеру, в нашем наборе данных есть 2 элемента, за время работы алгоритма будет выполнено 4 операции. Если в наборе 4 элемента, то операций будет 16. При 6 элементах будет 36 операций, и так далее.

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

let arr = [89, 14, 3, 847, 153, 219, 18, 24, 473];

function bubbleSort(arr) {
    let swapped;
    do {
        swapped = false;
        for (let i=0; i < arr.length-1; i++) {
            if (arr[i] > arr[i+1]) {
                let temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
      return arr;
}

bubbleSort(arr);

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

O(2^n) — экспоненциальное время

Экспоненциальную временную сложность мы можем наблюдать в алгоритмах, где количество вычислений удваивается при добавлении каждого нового элемента в набор данных. Так происходит, например, в брутфорс-решениях с использованием рекурсии. На маленьких наборах данных все работает отлично, но с увеличением числа элементов в наборе время выполнения может выйти из-под контроля.

Хорошим примером может служить рекурсивный расчет чисел Фибоначчи — такой, как в коде, приведенном ниже.

function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(4); // возвращает 3
fibonacci(5); // возвращает 5
fibonacci(6); // возвращает 8

O(n!) — факториальное время

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

2! = 2 x 1 = 2;
3! = 3 X 2 X 1 = 6;
4! = 4 x 3 x 2 x 1 = 24;
…
8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40320;

Как видите, число операций ужасно растет при каждом добавлении элемента в набор.

Хорошим примером алгоритма с факториальной временной сложностью может послужить простая рекурсивная функция. Эта функция принимает число в качестве входных данных и умножает его на факториал числа, меньшего на единицу. (В общем, стандартная функция для вычисления факториала числа, переданного в качестве инпута, — прим. ред. Techrocks). Как видите, время работы функции при незначительном увеличении входных данных растет просто катастрофически.

const factorial = n => {
    let num = n;

    if (n === 0) return 1
    for (let i = 0; i < n; i++) {
      num = n * factorial(n - 1);
    };

    return num;
  };

factorial(1); // 1 millisecond
factorial(5); // 120 millisecond
factorial(9); // 362880 millisecond
factorial(11); // 39916800 millisecond

Итоги

Когда ищете алгоритмическое решение задачи, важно учитывать временную сложность выбранного алгоритма. Не все алгоритмы одинаково производительны: некоторые могут быть эффективнее других в зависимости от величины обрабатываемого объема данных. А для сравнения эффективности алгоритмов применяется нотация большого «О».

[customscript]techrocks_custom_after_post_html[/customscript]

[customscript]techrocks_custom_script[/customscript]