Вы когда-нибудь слышали об истории «рис и шахматная доска»? Согласно историческим свидетельствам, эта история была впервые записана в 1256 году ученым по имени Ибн Халикан. История выглядит следующим образом:

Жил-был один индийский король, который любил играть в шахматы и регулярно вызывал мудрых посетителей на игру в шахматы. Однажды мимо проходил мудрец, и царь вызвал его на игру. Мудрец принял вызов царя. Король хотел мотивировать своего противника сильным стимулом, поэтому король сказал мудрецу, что, если мудрец выиграет, он может получить любую награду, которую пожелает, при условии, что он назовет ее заранее. Мудрец попросил что-то весьма необычное. Его награда была следующей: король должен был положить одно зернышко риса на первую шахматную клетку, а затем удваивать ее на каждую последующую, пока все клетки на шахматной доске не будут заполнены. Король принял просьбу мудреца, думая, что это наименьшая награда, о которой когда-либо мог просить любой из его противников.

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

Урок усвоен: экспоненты могут быть очень страшными.

— — —

Цель/Отказ от ответственности

Цель этой серии статей («Простые структуры данных и алгоритмы») — помочь всем «любителям обучения» развить интуитивное понимание концепций и тем DSA (структуры данных и алгоритмы). Я убежденный сторонник философии обучения, которую разделяли и Альберт Эйнштейн, и Ричард Фейнман. Эйнштейн однажды сказал: «Если вы не можете объяснить это 6-летнему ребенку, вы сами этого не понимаете». По сути, Фейнман сказал то же самое: «Если вы не можете объяснить что-то простыми словами, вы этого не понимаете. Лучший способ учиться — учить». Я искренне надеюсь, что в процессе написания этих статей я сам укреплюсь в своем концептуальном понимании DSA, и что многие другие также получат пользу от этого интуитивного понимания.

— — —

Необходимые знания

Чтобы иметь интуитивное представление об алгоритмической сложности и нотации Big O, необходимо иметь общее представление о нескольких темах:

— — —

У меня есть очень глупая иллюстрация для вас.

Представьте, что есть парень по имени Барт, который очень хорошо печет торты, а также имеет ТОННУ друзей.

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

Барт не хочет обидеть никого из своих друзей, создав впечатление, будто он предпочитает одних друзей другим, поэтому он решает испечь абсолютно ОГРОМНЫЙ торт, которым можно было бы накормить каждого из них.

Барту требуется некоторое время, чтобы закончить свой огромный торт, но он заканчивает его и дарит своим друзьям, надеясь, что они все будут счастливы. Однако его многочисленные друзья протестуют и говорят, что они не хотят гигантского общего торта, а скорее каждый хочет иметь торт ДЛЯ СЕБЯ. Каждый из них говорит Барту: «Если ты действительно мой друг, тогда ты должен испечь торт только для меня!»

После того, как Барту удается испечь торт для каждого из своих друзей, его «друзья» возвращаются к нему и говорят: «На самом деле, этого недостаточно. Мы с тобой не просто друзья, мы дружим и друг с другом, поэтому мы хотим, чтобы у каждой пары друзей был торт!»

Именно в этот момент Барт понял, что ему нужно найти новых друзей.

— — —

Прежде чем мы приступим к интуитивному пониманию алгоритмической сложности и нотации Big O, нам сначала нужно определить, что вообще означают эти термины!

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

Алгоритмическая сложность — это то, сколько ВРЕМЕНИ требуется алгоритму для выполнения задачи при заданном размере входных данных (обычно обозначается переменной "n"). Из моего глупого примера выше должно быть довольно легко увидеть, что выпечка торта для каждого отдельного друга имеет более высокую алгоритмическую сложность, чем выпечка одного торта, потому что, хотя один торт мог быть намного больше, чем отдельные торты, его размер по-прежнему постоянным, и общее время выпечки не сильно зависит от количества друзей Барта (при условии, что количество друзей очень и очень велико). Также должно быть легко увидеть, что выпечка торта для каждой пары друзей имеет гораздо более высокую алгоритмическую сложность, чем выпечка торта для каждого друга.

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

Обозначение Big O – это просто математический способ описания сложности алгоритма в обобщенном виде с использованием алгебраических терминов. Чтобы быть более конкретным, он описывает, как масштабируется время (или пространство памяти) при задании входной переменной.

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

Когда Барт испек один гигантский торт для всех своих друзей, мы можем описать сложность этого «алгоритма выпечки» как O(1). Почему? Потому что количество времени, которое требуется Барту для выполнения задачи, не зависит от размера ввода (количества друзей), особенно когда размер ввода очень велик.

Когда Барт пек пирог для каждого своего друга, мы можем описать сложность как O(n), потому что количество времени, которое Барт выполняет свою задачу, напрямую зависит (линейно) от размера входных данных. Больше друзей = больше тортов. Меньше друзей = меньше тортов.

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

— — —

Резюме

Подводя итог, что такое алгоритмическая сложность и нотация Big O? Алгоритмы — это процедуры или наборы шагов для выполнения задачи, а алгоритмическая сложность — это то, сколько времени требуется любому алгоритму для выполнения задачи при заданном размере входных данных. Поскольку компьютерные задачи имеют дело с очень большими входными данными, намного эффективнее оценивать и обобщать алгоритмическую сложность, используя нотацию Big O, которая использует алгебраические термины для описания того, как масштабируется время или объем памяти при задании входной переменной.

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

— — —

Ресурсы

Если вам нужна дополнительная помощь в получении интуитивного понимания алгоритмической сложности и нотации Big O, посмотрите эти видео:

Если вы хотите углубиться в теорию, применение и формальное понимание этих тем, ознакомьтесь со следующими статьями: