Обозначение Big O может напугать даже лучших программистов, но это не обязательно.

Недавно друг попросил меня объяснить им эффективность алгоритмов и нотацию Big O Notation. Эта подруга учится программировать, чтобы переключиться с роли в ИТ-инфраструктуре на роль в DevOps. Как и многие другие, ее пугала мысль о том, что на собеседовании ее спросят об эффективности. Любой, у кого нет формального образования в области компьютерных наук, тоже может испугаться, поэтому я покажу, почему Большого О нечего бояться.

Что такое Big O и почему он полезен?

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

Давайте посмотрим на пример:

Автомобиль А имеет двигатель мощностью 400 л.с. и весит 2850 фунтов. Между тем, автомобиль B имеет менее мощный двигатель мощностью 300 л.с., но при этом весит 2 000 фунтов.

Если разделить мощность на вес каждого из них, то передаточное отношение автомобиля A составит 0,14 л.с. / фунт, а передаточное отношение автомобиля B - 0,15 л.с. / фунт.

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

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

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

Как работает Big O?

По своей сути Big O - это анализ времени выполнения алгоритма с учетом роста входных данных. Следует помнить о нескольких вещах; во-первых, мы склонны смотреть на размер входных данных по мере их произвольного роста, а во-вторых, мы хотим рассмотреть наихудший сценарий. Каков наихудший сценарий для алгоритма? Это когда алгоритм выполняет максимальное количество шагов. Например, наихудший сценарий для алгоритма поиска - это когда весь набор данных пройден, а цель никогда не найдена. Почему мы смотрим на наихудший сценарий? Потому что, если мы планируем наихудшее, средний и лучший сценарии уже будут учтены.

Предупреждаю, в следующей части потребуется немного математики, но не расстраивайтесь! Это чисто предварительный расчет; Big O позволяет вам делать некоторые удобные предположения, которые могут «волноваться рукой». Точно так же, как соотношение мощности и веса игнорирует такие вещи, как аэродинамика, настройка подвески и целый ряд других факторов во имя простоты. Давайте посмотрим на несколько примеров, написанных в псевдокоде:

Пример 1:

Эта функция выполняется в так называемом «O из 1» или «постоянном времени», записанном как O (1). Это означает, что независимо от размера ввода функция всегда выполняет только заданное количество операций. На входе может быть массив длиной 10 или длиной 10 000, но единственный выполняемый шаг - вернуть первый элемент этого массива. В данном случае это одна операция, но даже если в анализируемом алгоритме было 100 операций, поскольку они выполняются только один раз, мы говорим, что алгоритм выполняется за O (1) раз.

Пример 2:

В этом примере выполняется линейный поиск в несортированном массиве и возвращается индекс первого экземпляра найденного элемента. Если элемента вообще нет в массиве, возвращается -1. Как указывалось ранее, Big O рассматривает наихудший сценарий, когда проверяется каждый элемент и совпадений не найдено. По мере роста массива сколько раз будет производиться сравнение в строке 3? Учитывая, что он находится внутри одного цикла for, который идет от начала до конца массива, мы можем определить, что это сравнение будет выполнено для каждого элемента массива. Это означает, что функция выполняется за «линейное время» или «O из N», записанное как O (N). По мере увеличения размера массива количество выполняемых им сравнений растет прямо пропорционально. Десять элементов в массиве? Десять сравнений. Миллиард элементов в массиве, миллиард сравнений.

Пример 3:

Здесь мы хотим определить, есть ли в несортированном массиве только уникальные элементы. Для этого мы сравниваем каждый элемент в массиве с каждым другим элементом в массиве. Опять же, наихудший сценарий, при котором выполняется наибольшее количество сравнений, - это когда массив уникален. В этом случае каждый элемент сравнивается с каждым другим элементом в строке 6 внутри вложенных циклов. Мы видим, что внешний цикл будет выполняться N раз, и для каждого из них внутренний цикл также будет выполняться N раз, что выражается как N * N. Это соответствует времени «O из N в квадрате», которое записывается как O (N²). Давайте посмотрим, как выглядит рост N для этого алгоритма:

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

Что нам делать со значением Big O, когда оно у нас есть?

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

Чем ближе линия к оси x, тем она эффективнее. Если у вас есть один алгоритм, который работает за O (N), а другой - за O (N²), вы знаете, что лучше всего использовать первый.

Является ли значение Big O гарантией производительности? Краткий ответ: нет. Возвращаясь к примеру с автомобилем, есть много реальных факторов, которые могут повлиять на производительность, которые игнорируются при сравнении отношения мощности к весу: аэродинамика, атмосферные условия, состояние трассы и т. Д. Для алгоритмов такие факторы, как скорость процессора, объем памяти, и многие другие могут определять реальную производительность приложения. Но для сравнения двух или более возможных способов разработки алгоритма Big O - лучший способ сделать это.

Также важно отметить, что программисты также не проводят такого рода анализ для каждой функции, которую мы пишем. Это просто полезный инструмент, который стоит держать в своем наборе инструментов. Используя его, вы узнаете определенные практические правила, например, следует избегать вложенных циклов, когда это возможно, чтобы избежать алгоритмов O (N²) или O (N³). Иногда эти замыслы неизбежны. А иногда это вообще не имеет значения. Если у вас есть алгоритм, в котором вы знаете, что размер входных данных постоянен или ограничен определенным значением, иметь значение O (N²) не так уж и плохо.

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

Приложив терпение и немного практики, вы сможете успешно пройти следующее техническое собеседование. Возможно, здесь, в Ordergroove, мы нанимаем! Https://www.ordergroove.com/careers/