Временная сложность алгоритмов. 

Введение

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

О большое, O малое, Омега и Тета

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

Существует 4 нотации для описания поведения функций относительно друг друга. Давайте разберемся с каждой из них.

Формальные математические определения этих нотаций следующие:

Теперь стало понятнее, что означают записи f(x) = O(g(x)) и f(x) = о(g(x)). Конечно, эти определения еще осмыслить нужно, но хотя бы термины «доминирует» и «растет не быстрее» дают надежду на понимание :)

Однако теперь в игру вступают еще две нотации: Омега и Тета.

Посмотрим на графиках, как ведут себя функции.

На первом графике мы наблюдаем, что с увеличением значения n функция f(n) растет медленней cg(n). То есть функция f(n) ограничена сверху функцией cg(n), а значит f = O(g).

На втором графике мы наблюдаем, что при увеличении n функция f(n) наоборот начинает расти быстрее функции cg(n) - график f располагается «над» графиком g. То есть функция f(n) ограничена снизу функцией cg(n), а значит f = Ω(g).

На третьем графика функция f(n) зажата между c1g(n) и c2g(n), то есть ограничена и сверху и снизу. Это и есть иллюстрация тетта-нотации.

Анализ алгоритмов

Теперь давайте переходить от теории к практике. Основное практическое применение этих нотаций в IT-индустрии - описание сложности алгоритмов.

Для оценки сложности алгоритмов принято использовать именно нотацию
«О большое». Когда говорят, что «сложность алгоритма равна O(g(n))» - это означает, что с увеличением количества входных данных (параметр n), количество операций или время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на функцию g(n).

Пример: если мы увеличим количество входных данных (допустим, размер массива) в 10 раз, во сколько раз вырастет количество операций? В 10? В 100? А может в 2 или 20? Именно такую оценку и позволяет дать описание сложности алгоритма.

Для начала посмотрим на сложность, описываемую разными функциями.

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

O(1) Константная сложность

Например, в цикле for мы перебираем константное число 10 следовательно алгоритм всегда сделает 10 шагов перед тем как выполниться.

Если код всегда выполняется за одно и тоже время, и никак не зависит от размера входных данных - это константная сложность.

void PrintHelloWorld()
{
    for (int i = 0; i < 10; i++)
    {
        Console.WriteLine("Hello world!");
    }
}

O(N) Линейная сложность

Если мы передадим в функцию некое число n, которое в цикле нужно передать, то кол-во шагов цикла перестанет быть константным и всегда будет завесить от того какую n мы передадим.

void PrintHelloWorld(int N)
{
    for (int i = 0; i < N; i++)
    {
        Console.WriteLine("Hello world!");
    }
}

Следовательно, число 10 заставить цикл совершить 10 шагов, а число 100 - 100 шагов.

O(log N) Логарифмическая сложность

Например, алгоритм бинарного поиска имеет логарифмическую временную сложность, поскольку он ищет половину входных данных при каждом сравнении.

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

int[] array = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 };
int x = BinarySearch(array, 8);

public static int BinarySearch(int[] array, int searchedValue)
{
    int left = 0;
    int right = array.Length - 1;
    //пока не сошлись границы массива
    while (left <= right)
    {
        //индекс среднего элемента
        int middle = (left + right) / 2;

        if (searchedValue == array[middle])
        {
            return middle;
        }
        else if (searchedValue < array[middle])
        {
            //сужаем рабочую зону массива с правой стороны
            right = middle - 1;
        }
        else
        {
            //сужаем рабочую зону массива с левой стороны
            left = middle + 1;
        }
    }
    //ничего не нашли
    return -1;
}

Как видно на каждой итерации количество элементов в рабочей области массива уменьшается вдвое. И если мы проанализируем кол-во элементов с кол-вом выполненных шагов, то заметим логарифмическую сложность log(16) + 1 = 5

Подробнее про бинарный поиск будет в этой статье (P.S. пока не готово)

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

O(N * log N) Линейно-логарифмическая сложность

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

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

void LinearLogarithmicComplexity(int array)
{
    //первый цикл со сложность O(N) 
    for (int i = 0; i < N; i++)
    {
        //второй цикл со сложность O(log N) 
        for (int j = 0; j < Math.Log2(array.Length); j++)
        {
            array[i] *= array[i];
        }
    }
}

У нас имеется массив размерностью N, мы проходимся по нему полностью = O(N)
Далее каждый i-ты элемент мы умножаем на себя logN раз.

Допустим наш массив имеет размер 8, следовательно N = 8, а logN + 1 = 4 , из этого следует 8 * 4 получаем 32 шага.

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

O(N^2) Квадратичная сложность

Время работы алгоритма с порядком роста O(N2) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность - повод пересмотреть используемые алгоритмы или структуры данных.

Проблема в том, что они плохо масштабируются. Например, если массив из тысячи элементов потребует 1 000 000 операций, массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, квадратичный алгоритм будет обрабатывать миллион элементов 32 года. Даже если он будет в сто раз быстрее, работа займет 84 дня.

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

static void SubquadraticComplexity(int N)
{
    for(int i = 0; i < N; i++)
        for( int j = 0; j < N; j++)
        {
            //какое-то дейсвие 
        }
}

O(2^N) Экспоненциальная сложность

Одним из примеров алгоритма с экспоненциальной сложностью является рекурсивная реализация последовательности Фибоначчи. Формула для n-го члена последовательности Фибоначчи: F(n) = F(n-1) + F(n-2), где первые два члена определены как F(0) = 0 и F(1) = 1 .

public int Fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

Этот алгоритм имеет экспоненциальную временную сложность O (2 ^ N), поскольку каждый вызов функции Фибоначчи приводит к двум новым рекурсивным вызовам, пока не будет достигнут базовый случай. В результате время, необходимое для вычисления F(n), растет экспоненциально с увеличением n. Это может сделать алгоритм очень медленным для больших значений n.

O(N!) Факториальная сложность

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

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

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

int set = {1,2,3};

//Некая функция для полного перебора всех возможных кобинаций и вывода
PrintCombinations(set);

//На выходе мы получим:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Как видно размер множеств это N = 3, перебор методом грубой силы займет у нас 3! = 6 операций.

Расчет сложности алгоритмов

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

Закон сложения для O-нотации

При сложении двух классов сложности складываются функции этих классов. Однако, O(f(n) + g(n)) приводит нас к большему из двух исходных классов – так как меньший член выражения просто отбрасывается.

Таким образом,

так как N растет быстрее, чем log N.

Это правило позволяет вычислить класс сложности для последовательности операций. Например, сначала мы выполняем выражение со сложностью O(f(n)), а следом за ним – O(g(n)). Тогда выполнение обоих выражений (одно за другим) будет иметь сложность O(f(n)) + O(g(n)), то есть O(f(n) + g(n)).

Закон умножения для O-нотации

Если мы повторяем N раз некоторый процесс с классом сложности O(f(N)), то результирующий класс сложности будет равен:

Предположим, некоторая функция f(...) имеет класс сложности O(N^2). Выполним ее в цикле N раз:

for(int i = 0; i < N; i++)
{
    f(...);
}

Сложность этого кода будет равна:

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

Как рассчитать if(...) else(...)

Отдельно разберем выполнение условий (if). Сначала выполняется само условие, а затем один из блоков (if или else).

if(test())
{
    // block1
}
else
{
    // block2
}

Предположим, что вычисление условия test имеет сложность O(T), блока block 1 – O(B1), а блока block 2 – O(B2).

Тогда сложность всего кода будет равна:

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

Подставим реальные значения:

• test – O(N),
• block 1 – O(N^2),
• block 2 – O(N).

и вычислим сложность кода:

Если бы операция test имела класс сложности O(N^3), то общая сложность кода составила бы O(N^3).

В O-нотации мы всегда отбрасываем менее значимые элементы.

Расчет сложности алгоритмов на C#

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

Возьмем код, который определяет, состоит ли список из уникальных значений (т.е. нет ли в нем дубликатов). Размер списка обозначим как N, а сложность операции сравнения элементов примем за O(1).

Список уникален, если каждое его значение не встречается ни разу «справа» от элемента. Для значения array[i] «правым» фрагментом списка будет срез array[i+1]

static bool IsUnique(int[] array)
{
    for(int i = 0; i < array.Length - 1; i++)
        if (array[i] == array[i + 1])
            return false;

    return true;
}

Определим сложность для каждой строки функции:

1. Сложность операции return - O(1)
2. Сложность создания среза - O(N)
3. Сложность проверки in - O(N)
4. Сложность создания for и получения индекса - O(1)

Таким образом, полная сложность цикла (по ранее рассмотренному нами правилу) равна:

O(N)*(O(N)+O(N)+O(1)) = O(N)*O(N) = O(N^2)

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

Эпилог

Итак, давайте подведем итог, что же мы узнали:

1. Запись f(x) = O(g(x)) обозначает, что функция f(x) ограничена сверху функцией g(x) (т.е. растет медленнее или также).
2. Запись f(x) = о(g(x)) обозначает, что функция g(x) доминирует над функцией f(x) (т.е. отношение функций стремиться к 0)
3. Запись f(x) = Ω(g(x)) обозначает, что функция f(x) ограничена снизу функцией g(x) (т.е. растет быстрее или также)
4. Запись f(x) =θ(g(x)) обозначает, что функция f(x) ограничена и сверху, и снизу функцией g(x).

Основные правила расчета сложности алгоритмов:

• Сложение

• Умножение

• Расчет сложности блока if:

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

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

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

Если Вы хотите получать еще больше интересных материалов по программированию, IT, C#, .NET, ASP.NET, .NET Core и другими связанными продуктами, то подписывайтесь на наш Telegramm канал.