Полное руководство по временной сложности алгоритмов для Руби-разработчиков

Это перевод оригинальной статьи от Jesus Castello.

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

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

Вы сможете применить это знание к своему коду.

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

Но для начала, мы должны обсудить, что такое медленно и быстро.

Сортировка одного миллиона чисел за 150 мс (миллисекунд) это медленно или быстро?

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

На самом деле, мы хотим узнать, как быстро будет работать алгоритм по мере роста «размера входных данных».

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

Использую нотацию через «О» большое, мы сможем классифицировать алгоритмы по их производительности.

Это выглядит как-то так:

Здесь представлен алгоритм константного типа.

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

Другой тип — линейные алгоритмы:

Здесь «n» представляет размер входных данных (размер строки, массива и т.д.) Это означает, что он будет тратить время в соотношении 1:1 к размеру входных данных, таким образом, что удвоение количества входных данных, приведёт к удвоению времени работы алгоритма.

(Большинство, но далеко не все, — прим. пер.)

Всегда занимает одно и то же время

Объём работы делится на 2 после каждой итерации цикла (пример: бинарный поиск)

Время на совершение работы растёт в соотношении 1:1 от размера входных данных

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

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

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

Время на выполнение таких алгоритмов растёт в степени n к размеру входных данных. Это гораздо медленнее, чем квадратичный алгоритм, так что не путайте их. Одним из примеров может служить рекурсивный алгоритм Фибоначчи.

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

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

Вы не можете пропускать числа, потому что вы можете упустить те, которые ищете. Так что, это условие делает данный алгоритм линейным — O(n).

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

Мы собираемся исследовать три примера кода для проверки решений в игре Scrabble.

Scrabble — это игра, которая получив список символов (пример: o, l, l, h, e), просит вас сложить слово (пример: hello) используя эти символы.

Знаете ли вы временную сложность этого кода? Ключ для понимания — метод count, так что убедитесь, что вы понимаете, что этот метод делает.

Правильный ответ: O(n²).

И причина этого в том, что методом each_char мы перебираем каждую букву в строке word. Если бы мы использовали только этот метод, это был бы линейный алгоритм O(n). Но внутри блока мы вызываем метод count.

Этот метод, по сути, является ещё одним циклом, который перебирает символы в строке, чтобы подсчитать их.

Ладно.

Можно ли нам сделать это лучше? Если ли способ избавить нас от этого зацикливания?

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

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

Но если искомые символы оказываются в конце, в порядке, обратном тому, как они могут находиться в word, производительность может оказаться на уровне первой версии с count, так что мы можем сказать, что это всё ещё квадратичный алгоритм — O(n²).

Нам не нужно беспокоиться о случае, когда нет ни одного из искомых символов в word, потому что метод all? остановится, как только sub! вернёт false. Но вы можете узнать об этом только если будете изучать Руби глубже, чем это дают на обычных курсах.

Что если мы исключим любые виды циклов внутри блока? Мы могли бы использовать хэши вместо них.

Чтение и запись значений хэша это всегда константная операция — O(1), что достаточно быстро, особенно в сравнении с циклами.

Один строит хэш, второй проверяет её. Но так как эти два цикла не вложены друг в друга, это линейный алгоритм — O(n).

Если мы проведём бенчмарк этих трёх решений, мы увидим, что наш анализ соответствует результатам:

Вот линейный график:

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

Надеюсь, вы узнали что-то новое и интересное для вас!

Спасибо, что прочитали до конца.