👨‍🎓️ Алгоритмы и структуры данных на C++ для новичков. Часть 1: Основы анализа алгоритмов

Осваиваем основы анализа алгоритмов, которые потребуются любому начинающему программисту на C++ (и не только). Адекватное представление о времени выполнения кода может оказаться решающим фактором там, где производительность имеет большое значение.

Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

  1. углубишься в решение практических задач;
  2. узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.

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

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

***
Цель цикла
Этот цикл статей представляет собой краткое введение в алгоритмы и структуры данных. Будучи кратким руководством, он не является исчерпывающим пособием, а охватывает только самые важные темы. Целевая аудитория – читатели, желающие узнать об алгоритмах, но не имеющие времени на чтение книг, глубоко освещающих этот предмет. Например, серия должна заинтересовать читателей, готовящихся к предстоящему собеседованию. Статьи не требуют от читателя предварительной подготовки, связанную с алгоритмами и структурами данных, но определенные знания в программировании на C++ необходимы.

Что такое алгоритм?

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

Важность алгоритмов в информатике трудно переоценить. Они позволяют программисту реализовать эффективные, надежные и быстрые решения за короткий промежуток времени. Почти любые сложные программы на современных компьютерах в значительной степени опираются на алгоритмы. Операционные системы пользуются алгоритмами планирования, которые организуют и распределяют процессорное время между процессами, создавая иллюзию, что они выполняются одновременно. Многие умные алгоритмы, такие как растеризация, отсечение, back-face culling и сглаживание, служат для создания потрясающих 3D-миров в реальном времени. Алгоритмы позволяют найти кратчайший маршрут к месту назначения в городе, содержащем тысячи улиц. Благодаря алгоритмам машинного обучения произошла революция в таких областях, как распознавание изображений и речи. Перечисленные алгоритмы – это только вершина айсберга, и изучение этого предмета откроет множество дверей в карьере программиста.

Больше полезной информации вы найдете на нашем телеграм-канале «Библиотека программиста».

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

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

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

  • Сохраняет значение элемента во временной переменной;
  • Перемещает все элементы, которые больше чем вставляемый элемент (расположенные перед этим элементом) на одно место вправо;
  • Помещает значение временной переменной в освободившееся место.

Давайте подробнее рассмотрим этот процесс на примере:

Здесь, единственный элемент, который осталось вставить в отсортированный подмассив – это 4. Мы сохраняем это значение во временною переменную.

Мы сравниваем 4 с 7, и поскольку 7 больше, мы копируем его на позицию справа (значения, которые мы сравниваем с вставляемым элементом, обозначены фиолетовым).

Сравниваем 4 с 6, и поскольку 6 больше, копируем его на позицию справа.

Сравниваем 4 с 5, а поскольку 5 тоже больше чем 4, его тоже копируем его на позицию справа.

Наконец, мы сравниваем 4 с 3, и так как 3 меньше чем 4, мы присваиваем значение временной переменной на позицию рядом с ним. И теперь наша работа выполнена; мы расположили 4 в правильное положение.

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

PseudocodeInsertionSort
n ← Array.size
For i=2 to n
    j ← i – 1
    temp ← Array[j]
    While Array[j-1]>temp and j>0
        Array[j] ← Array[j-1];
        j ← j-1
    Array[j] ← temp

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

InsertionSort.cpp
void insertionSort(int *array, int n)
{
    for(int i=2;i<=n;++i)
    {
        int j=i-1;
        int temp = array[j];
        while(array[j-1]>temp)
        {
            array[j]=array[j-1];
            --j;
        }
        array[j]=temp;
    }
}

Основы анализа

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

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

Абстрактная модель машины

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

Асимптотический анализ

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

Те же вопросы можно задать и о производительности алгоритма в различных условиях. Для большинства алгоритмов размер входных данных не является единственным фактором, но особенности входных данных также влияют на время выполнения. В качестве примера можно привести линейный поиск. Это простой алгоритм для нахождения элемента в списке. Он последовательно проверяет каждый элемент списка до тех пор, пока не обнаружит совпадение или пока не просмотрит весь список. Очевидно, что время работы этого алгоритма может резко отличаться для списков с одинаковым размером n. В лучшем случае, если искомый элемент является первым в списке, алгоритму требуется только одно сравнение. С другой стороны, если в списке отсутствует нужный элемент или он оказался последним, алгоритм выполнит ровно n сравнений. В целом, при анализе используется один из следующих двух подходов: либо можно считать входные данные случайными и анализировать среднюю производительность, либо мы можно подобрать худшие входные данные и исследовать наихудшую производительность. В этой серии статей мы будем придерживаться анализа наихудшего случая, поскольку это гарантирует, что для любого примера входных данных размера n время работы не превысит полученного предела. Кроме того, как мы определяем "средние" данные, может повлиять на результат анализа.

«O» большое

Асимптотический анализ позволяет оценить производительность алгоритмас точки зрения того, как время (или память), занимаемое алгоритмом,увеличивается с возрастанием количества входных данных. В асимптотическихобозначениях используется функция для описания отношения междупроизводительностью алгоритма и размером задачи, когда она становится большой.В связи с коротким характером статьи мы ограничимся только большим "O" и незатронем многие нюансы асимптотического анализа. Говоря простым языком, еслисложность алгоритма равна O(n2), это означает, что время работы увеличивается какквадрат размера входных данных n. Таким образом, если размер входных данныхравен n, время выполнения приблизительно составляет n2. Другими словами, есливы удвоите размер входных данных, то время выполнения возрастет примерно вчетыре раза. Ниже приведены основные правила для вычисления большого "O"алгоритма:
1. Если алгоритм требует f(n) примитивных операций, то он имеетсложность O(f(n)).2. Если алгоритм выполняет операцию, которая занимает f(n)g(n) раз, топроизводительность алгоритма составляет O(f(n)g(n)).3. Если алгоритм имеет сложность cO(f(n)), где c - константа, то егосложность можно упростить до O(f(n)). Иначе говоря, константы можноопускать.4. Если алгоритм выполняет операцию, которая занимает O(f(n)) шагов, азатем выполняет другую процедуру, которая занимает O(g(n)) шагов, тообщая производительность алгоритма равна O(f(n)+g(n)).5. Если алгоритм имеет сложность O(f(n)+g(n)) при этом g(n)<f(n), длябольших n, то его сложность можно упростить до O(f(n)).

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

Пример правила 1: Взгляните на реализацию алгоритма, который вычисляет сумму всех элементов в массиве, на языке C++.

sum.cpp
int sum(int* array, int n)
{
    int sum = 0;
    for(int i=0;i<n;++i)
    {
        sum+=array[i];
    }
    return sum;
}
Данная программа выполняет одно присваивание до начала цикла, n присваиванийвнутри цикла и возвращает сумму после. Таким образом, для выполнения требуетсяn+2 простых операций. Поэтому, согласно правилу 1, ее сложность равна O(n+2).

Пример правил 2 и 3: Приведенная ниже программа складывает две квадратные матрицы.

matrixAddition.cpp
void matrixAddition(int** m1, int** m2, int** dest, int n)
{
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            dest[i][j]=m1[i][j]+m2[i][j];
        }
    }
}
Этот алгоритм состоит из двух вложенных циклов. Внутренний цикл выполняет nитераций, причем каждый шаг состоит из двух простых действий: сложения иприсваивания. Применяя правило 2, можно сделать вывод, что сложностьвнутреннего цикла равна O(2n). Внешний цикл также делает n итераций, но вместоиспользования простых операций он запускает внутренний цикл. Повторноприменив правило 2, мы заключаем, что внешний цикл (а значит и алгоритм) имеетсложность O(n2n)=(2n2). Также по правилу 3 можно избавиться от константы,и получить O(n2). Константные множители можно опустить, поскольку они невлияют на асимптотическое поведение алгоритма. Однако они имеют большоепрактическое значение, поскольку алгоритм с той же сложностью, но вдвое быстрее,всегда предпочтительнее.

Пример правил 4 и 5: Обратите внимание на программу ниже

function.cpp
void function(int** dest, int n)
{
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            dest[i][j]=1;
        }
    }

    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            for(int k = 0; k < n; ++k)
            {
                dest[i][j]=2;
            }
        }
    }
}
Эта процедура выполняет дважды вложенный цикл с суммарной сложностью O(n2),а затем трижды вложенный цикл со сложностью O(n3). В соответствии с правилом 4сложность алгоритма составляет O(n3+n2). А поскольку n3 больше, чем n2, мыможем уменьшить сложность до O(n3), применив правило 5. С математическойточки зрения, утверждение, что одна функция больше другой, не имеет смысла. Валгоритмическом анализе f(n)<g(n) означает, что g(n) становитсянезначительной по сравнению с f(n), когда n становится очень большой. Поэтомуговорят, что f(n)+g(n) и f(n) асимптотически эквивалентны, а g(n) можноудалять. Не обращая внимания на меньшие функции, мы можем избежать анализамелких задач по подготовке и очистки программы и сосредоточиться наасимптотическом поведении при увеличении входных данных. Тем не менее,практическое время работы алгоритма иногда может значительно отличаться от еготеоретического поведения. Рассмотрим два алгоритма, первый из которых имеетсложность O(logn), и выполняет logn+1000000000 реальных шагов.Сложность второго алгоритма составляет O(n2), а на практике требует n2+10операций. Несмотря на то, что асимптотическая сложность первого алгоритмадовольно низкая, он будет выполняться намного медленнее, если входные данныене очень большие.

Часто встречающиеся функции времени выполнения

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

O(1) - Если алгоритм выполняет одинаковое количество операций в независимости от размера входных данных, он имеет сложность O(1).O(logn)Когда сложность алгоритма логарифмическая, программа становится лишьнемного медленнее по мере роста n. При умножении размера входных данных накоэффициент основания логарифма время выполнения увеличивается только на константу.Чтобы понять, насколько медленно растет время выполнения, подумайте о том, сколькобит требуется для хранения n. Поскольку это количество равно log2(n+1), логарифмическое время работы пропорционально числу битов, используемыхдля хранения n. При умножении диапазона на два число битов увеличивается наединицу. Аналогично, при увеличении размера входных данных в два раза времяработы увеличивается на единицу. Например, когда размер входных данныхравен миллиарду, время выполнения равно 30, а когда размер входных данных равендвум миллиардам, она равно 31. Поскольку logbn=loganlogab, где 1logba -константа, основание логарифма в нотации большого «О» обычно опускается.Логарифмическое время работы характерно для программ, которые преобразуютбольшую задачу в серию меньших задач, каждый шаг которых делит размер задачина постоянную величину. Примером алгоритма, имеющего такую сложность,является двоичный поиск. Двоичный поиск - это эффективный метод нахожденияэлемента в отсортированном списке. Он работает путем сравнения целевогозначения с элементом в середине. Поскольку список отсортирован, искомый элементдолжен находиться справа, если целевое значение больше среднего элемента. Еслизначение искомого элемента меньше, то он должен быть слева. Это знание позволяетисключить половину искомой области в каждой итерации.O(n) - Если время выполнения программы является линейным, то обычно каждыйвходной элемент подвергается обработке с постоянной сложностью. Когда n равномиллиону, время работы также равняется миллиону. Если n удваивается, времяработы также удваивается. Для алгоритма, который должен обработать все nисходных данных, такая ситуация является оптимальной. Нахождение наибольшегоэлемента в несортированном списке является примером такой случая, при которомкаждый элемент рассматривается и сравнивается с текущим максимумом.O(nlogn) - O(nlogn) растет быстрее чем линейная функция, но ненамного. Такаясложность обычно возникает, когда алгоритм разбивает проблему на подзадачи,решает их и объединяет решения. Этот подход к разработке алгоритмов называется "разделяй и властвуй". O(nlogn) является оптимальным для алгоритмов сортировкина основе сравнения. В дальнейшем мы более подробно рассмотрим алгоритмы"разделяй и властвуй" и алгоритмы сортировки.
O(n2) - В случае, когда алгоритм перебирает все входные данные и на каждойитерации перебирает их снова, он имеет квадратичную сложность. В качествепримера рассмотрим программу, которая выводит все возможные пары из элементовмассива:
displayPairs
void displayPairs(int* array, int n)
{
    int count = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            count++;
            cout<< "Pair #"<<count<<':'<< array[i] <<'-' << array[j] <<endl;
        }
    }
}
Чтобы отобразить все пары, каждый элемент массива должен быть сопряжен скаждым другим элементом. Алгоритмы с квадратичной сложностью практичнытолько при средних или малых размерах входных данных. Когда сложностьалгоритма равна O(nk), где k - константа, говорят, что он имеет полиномиальноевремя выполнения. В эту категорию входят линейные, квадратичные, кубические идаже сложность O(n100). На деле, полиномиальные времена выполнения высокогопорядка встречаются редко, но они быстрее, чем экспоненциальные ифакториальные времена выполнения.
O(2n) - Несмотря на то, что такие алгоритмы возникают естественным образом при решении многих задач методом перебора, лишь немногие алгоритмы с экспоненциальным временем работы пригодны для практического использования, поскольку они растут чрезвычайно быстро. При добавлении одного входного элемента время выполнения удваивается! Само собой разумеется, что такие алгоритмы бесполезны, если только размер входных данных не очень мал. Программы, решающие задачу о ранце, являются примерами алгоритмов с экспоненциальной производительностью. В простейшей вариации этой задачи даются n предметов, имеющих вес и ценность и рюкзак, с ограниченной вместимостью. Ваша цель - уложить как можно большое число ценных вещей в рюкзак. Каждый предмета имеет два состояния: предмет кладётся в рюкзак, либо предмет не кладётся. Таким образом, существует 2n комбинаций, и алгоритму нужно столько же шагов, чтобы перебрать их.
O(n!) - Факториал - самая быстрорастущая сложность, которую встречается напрактике. Эта функция растет гораздо быстрее, чем даже экспоненциальная функция.Для сравнения, когда размер входных данных составляет всего 62, то количествовыполняемых операций превышает количество атомов в обозримой Вселенной!Большинство алгоритмов с факториальной сложностью расставляют входныеданные в оптимальном порядке. Если есть n связанных городов, задача "Путешествиекоммивояжера", просит вас проложить между ними кратчайший замкнутый маршрут,проходящий через каждый город только один раз. Самый очевидный способ -перебрать все возможные варианты. Если все города связаны между собой (двагорода связаны, если из одного положено дорога в другой), то у вас есть n вариантовдля выбора первого города в маршруте, n1 для второго, n2 для третьего и так далее.Таким образом, общее количество комбинация равно n!

Визуализация функций

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

На приведенном ниже изображении показаны графики распространенных функций времени выполнения.

Заключение

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

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

matyushkin
29 марта 2020

ТОП-10 книг по C++: от новичка до профессионала

Книги по C++ на русском языке с лучшими оценками. Расставлены в порядке воз...
admin
21 февраля 2017

Какие алгоритмы нужно знать, чтобы стать хорошим программистом?

Данная статья содержит не только самые распространенные алгоритмы и структу...