Алгоритмы (теория/практика): Часть 4. Начинаем анализировать

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

Алгоритм линейного поиска

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

Если мы находим совпадение – возвращаем номер первого, в противном случае, возвращаем -1. (В C++ мы должны обязательно указать тип возвращаемого значения, логично было бы возвращать 0, но ведь 0 – это позиция первого элемента, поэтому вернём -1 в случае неудачи, чтобы избежать путаницы.)

int linear_search(int arr[], int n, int target)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }

    return -1;
}

Замечание: функция linear_search принимает три аргумента – массив целочисленных значений, длину массива, искомое значение и возвращает позицию элемента, либо -1, в случае, если элемент не был найден. Для перебора массива используется стандартный цикл for.

Анализ

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

В таких случаях обычно описывают время работы в худшем случае, в лучшем случае и среднее время работы. Под лучшим случаем подразумеваем, что искомый элемент находится в самом начале массива, в худшем — что элемента нет вовсе (либо он в самом конце). В качестве среднего случая на данный момент возьмём количество операций в худшем случае, разделённое на 2. Это не совсем корректное определение, но мы к нему еще вернёмся.

Худший случай

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

1. \(n+1\) сравнений i с \(n\);
2. \(n\) сравнений искомого значения с просматриваемым;
3. \(n\) операций инкремента (i++);
4. 1 возврат значения;
5. Также будет произведена 1 операция инициализации. Мы не будем рассматривать её как две разных — объявление и присваивание значения, а договоримся, что это одна единственная операция;

Замечание: порядок выполнения цикла for: сначала происходят объявления переменных, после чего проверяется условие, далее выполняется тело цикла и в самом конце происходит инкремент/декремент счетчика. Начиная со второй итерации всё происходит в том же порядке, кроме объявления переменных. Проверка условия выполняется перед телом цикла и перед инкрементом, именно поэтому она происходит 1 лишний раз.

Просто суммируем:

Вспоминаем пункт порядок роста и понимаем, что асимптотическая сложность в худшем случае будет равна \(\Theta (n)\). Как видно, характер роста сложности линейный, что значит, что с увеличением входных элементов прямо пропорционально возрастёт и количество необходимых операций, а значит и время работы.

Лучший и средний случаи

В лучшем случае, когда элемент находится в самом начале, мы получаем:

1. 1 инициализация переменной (int i = 0);
2. 1 операция сравнения i с \(n\);
3. 1 операция сравнения искомого значения с просматриваемым;
4. 1 возврат значения;

Итого 4 операции. В такой ситуации асимптотическую сложность обозначают как \(\Theta (1)\) и это означает, что время работы алгоритма будет чистом постоянным вне зависимости от размера входных данных.

В среднем же алгоритму придется выполнить \(\dfrac { 3n+3 }{ 2 } \), а значит в этом случае сложность равна \(\Theta (n)\).

Подытожим:

• Сложность в лучшем случае: \(\Theta (1)\);
• Сложность в худшем случае: \(\Theta (n)\);
• В среднем: \(\Theta (n)\);

Осторожность: если вдруг кто-то задается вопросом, почему в среднем случае сложность равна не \(\Theta (\frac { n }{ 2 } )\), а \(\Theta (n)\), советую вспомнить пункт «порядок роста» и понять, что асимптотическая сложность призвана описать характер роста, а не точное время работы. В нашем случае, с увеличением \(n\) в 2 раза сложность также увеличится в два раза. Поэтому деление на 2 нас не интересует.

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

Алгоритм двоичного поиска

Алгоритм двоичного поиска несколько сложнее линейного, но, тем не менее, его описание также не является чем-то экстраординарным. Давайте для начала опишем его суть.

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

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

Код будет примерно такой:

int binary_search(int arr[], int start, int end, int target)
{
    if (start == end)
    {
        return arr[start] == target ? start : -1;
    }

    int mid = floor(start + (end - start) / 2);

    if (target <= arr[mid]) 
    { 
        // Левая часть 
        return binary_search(arr, start, mid, target); 
    } 
    else 
    { 
        // Правая часть 
        return binary_search(arr, mid + 1, end, target); 
    } 
} 

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

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

Если длина массива равна единице, то мы добрались до одного элемента, а значит у нас есть два варианта – вернуть индекс, если искомое значение найдено, либо -1, если нет. При единичном массиве индексы start и end идентичны, поэтому можно было взять любой.

Если же длина больше 1, то находится средний индекс, который необходимо округлять, в случае, если длина массива кратна 2. Я выбрал функцию floor, которая округляет в меньшую сторону, но это не принципиально.

Далее мы сравниваем искомое значение с серединным (не индексом, а со значением) и если искомое попадает в левую часть, то рекурсивно вызываем эту же функцию, но в качестве начала и конца массива используем начальный индекс и серединный соответственно. Если в правую часть – то началом и концом массива уже будет индекс, следующий за серединным, а также конечный.

Еще раз хочу, чтобы вы проследили логику:

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

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

Замечание: рекурсия – это вызов функции внутри самой себя. Посмотрите на код еще раз. Функция выполняется и в определенный момент натыкается на оператор return, который прерывает выполнение функции и возвращает значение, находящееся справа от оператора. Этим значением является результат выполнения функции. Происходит еще один вызов функции, и управление передается именно ей. Мы оказываемся на новом уровне рекурсии. Выполнение же на предыдущем останавливается ровно на том же месте, где и произошёл вызов. Далее вызовы происходят до тех пор, пока не будет возвращено какое-либо одиночное значение. Далее происходит выход из рекурсии в обратном порядке. То есть, функция сначала завершается на самом глубоком уровне, а затем постепенно доходит до самого верха, который также завершает исполнение и возвращает значение уже вызвавшей её функции (main, например).

Анализ

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

Так что давайте пройдемся и подсчитаем количество сравнений в двоичном поиске, затем попытаемся описать это при помощи уже знакомых нам обозначений. На каждой итерации массив уменьшается в два раза, затем происходит 1 сравнение. Это продолжается до тех пор, пока значение не будет равно 1, после чего произойдет еще одно сравнение. Как же найти время выполнения? Давайте просто немного подумаем. Учитывая, что каждый раз происходит новое деление на 2 до тех пор, пока число не будет равняться 1, то исходное количество элементов можно найти умножением 1 на 2 то же самое количество раз. Чтобы с 8 дойти до 1 нам нужно поделить 8 на 2 три раза – 4, 2, 1. Чтобы из 1 дойти до 8, нужно умножить 1 на 2 три раза – 2, 4, 8.

Выходит, что

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

А значит, что общее количество сравнений будет описываться функцией

А отсюда следует, что

Какой отсюда можно сделать вывод? А он напрашивается сам собой - логарифмическая функция растет намного медленнее, чем линейная. Если в алгоритме линейного поиска мы увеличиваем задачу в два раза (подаем на вход массив в два раза больше), то и объем работы в худшем случае увеличивается в два раза. В то же самое время, двоичному поиску придется выполнить лишь на одно действие больше.

Допустим, у нас массив из 512 значений (используем асимптотическую сложность). Линейный поиск в худшем случае сделает 512 сравнений. Двоичный же поиск сделает всего 9 сравнений. Теперь если мы увеличим задачу в два раза, то линейный поиск уже сделает 1024 сравнения в худшем случае, а двоичный всего лишь 10. Чувствуете разницу? Двоичный поиск намного выгоднее, чем линейный. Всё еще сомневаетесь в целесообразности изучения алгоритмов?

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

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

Следующая статья

Предыдущая статья