Давайте упростим сложность алгоритма!

1656650300 davajte uprostim slozhnost algoritma

от Шрутти Танвар

1*C9fLwET5OfP4H3GuN0f-SQ

Прошло некоторое время с тех пор как я начал думать о том, чтобы вернуться к основам и очистить основные концепции информатики. И я подумал, что перед тем, как перейти к группе трудных тем, таких как структуры данных, операционные системы, ООП, базы данных и дизайн системы (серьезно, список бесконечен)?, я, вероятно, должен выбрать тему, которую мы все кое-что не хотим прикосновения: алгоритм анализа сложности.

Да! Концепция, которую большинство времени игнорируют, потому что большинство из нас, разработчиков, думают: «Хм, может быть, мне не понадобится это знать, пока я фактически кодирую!».?

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

Что вообще такое анализ алгоритмов и зачем он нужен??

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

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

Давайте возьмем пример. Предположим, у нас есть функция продукт() который умножает все элементы массива кроме элемента с текущим индексом и возвращает новый массив. Если я прохожу [1,2,3,4,5] как входные данные я должен получить [120, 60, 40, 30, 24] как результат.

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

Вы можете следить? Прекрасно!

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

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

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

Мы можем смело заключить, что последний алгоритм работает лучше, чем первый. Все идет нормально? Идеально!

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

В зависимости от того, когда анализируется алгоритм, то есть до внедрения или после внедрения, анализ алгоритма можно разделить на два этапа:

  • Априорный анализ − Как следует из названия, априори(предыдущий), мы проводим анализ (пространственный и временной) алгоритм перед его запуском в конкретной системе. Следовательно, по сути это теоретический анализ алгоритма. Эффективность алгоритма измеряется в предположении, что все другие факторы, например скорость процессора, постоянны и не влияют на реализацию.
  • Апостиарный анализ − Апостиарный анализ алгоритма выполняется только после его запуска в физической системе. Выбранный алгоритм реализован с помощью языка программирования, выполняемого на целевой компьютерной машине. Это напрямую зависит от конфигурации системы и изменений от системы к системе.

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

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

Глубокое погружение в сложность с помощью асимптотического анализа

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

Итак, если вы хотите запустить алгоритм с набором данных размера пнапример, мы можем определить сложность как числовую функцию f(n) — время против размера входных данных п.

1*8jALHD5cvsBd81r916YclA@2x
Время против входных данных

Теперь вы, наверное, задаетесь вопросом: не возможно ли, чтобы алгоритм занимал разное количество времени на тех же входных данных, в зависимости от таких факторов, как скорость процессора, набор инструкций, скорость диска и марка компилятора? Если да, то погладьте себя по плечу, потому что вы совершенно правы!?

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

Анализ сложности выполняется по двум параметрам:

  1. время: Временная сложность дает указание на то, сколько времени требуется для выполнения алгоритма с учетом размера входных данных. Ресурс, который нас волнует в этом случае, это ЦБ (и время настенных часов).
  2. Космос: Сложность пространства схожа, но указывает на то, сколько памяти «нужно» для выполнения алгоритма относительно размера входных данных. Здесь мы сталкиваемся с системной оперативной памятью как ресурсом.

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

Большой О (Большой О)
Первой и популярной нотацией, используемой для анализа сложности, является нотация BigO. Причина этого в том, что он дает анализ наихудшего случая алгоритма. Вселенная ботанов в большинстве своем озабочена тем, насколько плохо может вести себя алгоритм и как его можно улучшить. BigO дает нам именно это.

Давайте углубимся в математическую сторону, чтобы понять суть вещей.

1*WH9HVd8jV7N4dbUR5jsttg@2x
BigO (самый точный верхний предел функции)

Рассмотрим алгоритм, который можно описать функцией f(n). Итак, чтобы определить BigO of f(n)нам нужно найти функцию, скажем, g(n), которая его ограничивает Это означает, что после определенного значения, n0, значение g(n) всегда будет превышать f(n).

Мы можем записать это как,
f(n) ≤ C g(n)
где n≥n0; C>0; n0≥1

Если вышеуказанные условия выполняются, мы можем это сказать g(n) является BigO of f(n), или
f(n) = O(g(n))

Можем ли мы применить то же самое для анализа алгоритма? Это в основном означает, что в худшем случае выполнение алгоритма значения не должно превышать определенную точку g(n) в этом случае. Итак, g(n) является BigO of f(n).

Давайте разберемся с некоторыми распространенными обозначениями bigO и их сложностью и поймем их получше.

  • O(1): Описывает алгоритм, который будет всегда выполняться в то же время (или пространство) независимо от размера входного набора данных.
function firstItem(arr){      return arr[0];}

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

Связывая это с приведенным выше объяснением, даже в самом худшем случае этого алгоритма (предполагая, что входные данные будут чрезвычайно большими), время работы будет оставаться постоянным и не будет выходить за пределы определенного значения. Следовательно, его сложность BigO постоянна, то есть O(1).

  • O(N): Описывает алгоритм, производительность которого будет расти линейно и прямо пропорционально размеру входных данных. Посмотрите на примере ниже. У нас есть функция под названием matchValue(), который возвращает истину всякий раз, когда в массиве найден соответствующий регистр. Здесь, поскольку мы должны повторить весь массив, время работы прямо пропорционально размеру массива.
function matchValue(arr, k){   for(var i = 0; i < arr.length; i++){     if(arr[i]==k){       return true;     }     else{       return false;     }   }   }

Это также демонстрирует, как Big O предпочитает худший сценарий эффективности. Соответствующий регистр можно найти во время любой итерации for цикла, и функция вернется раньше. Но нотация Big O всегда предполагает верхний предел (наихудший случай), когда алгоритм будет выполнять максимальное количество итераций.

  • O(N²): Это представляет собой алгоритм, производительность которого прямо пропорциональна квадрату размера входного набора данных. Это типично для алгоритмов, включающих вложенные итерации над набором данных. Более глубокие вложенные итерации приведут к O(N³), O(N⁴) и т.д.
function containsDuplicates(arr){    for (var outer = 0; outer < arr.length; outer++){        for (var inner = 0; inner < arr.length; inner++){            if (outer == inner)                 continue;            if (arr[outer] == arr[inner])                return true;        }    }       return false;}
  • O(2^N): Указывает алгоритм, рост которого удваивается с каждым добавлением к входному набору данных. Кривая рост функции O(2^N) экспоненциальна — начинается очень мелко, а затем стремительно растет. Примером функции O(2^N) является рекурсивное вычисление чисел Фибоначчи:
function recursiveFibonacci(number){    if (number <= 1) return number;    return recursiveFibonacci(number - 2) + recursiveFibonacci(number - 1);}

Вы понимаете это? Если нет, смело задавайте свои вопросы в комментариях ниже. 🙂

Двигаясь дальше, теперь, когда мы имеем лучшее понимание нотации BigO, перейдем к следующему типу асимптотического анализа, которым является Большая Омега (Ω).

Большая Омега (Ω)?
ТBig Omega(Ω) дает нам лучший сценарий выполнения алгоритма. Это означает, что это даст нам минимальное количество ресурсов (времени или пространства), необходимых для работы алгоритма.

Давайте погрузимся в его математику, чтобы проанализировать это графически.

1*X5E8pk9w3caz2qrrwug58w@2x
BigΩ (самый точный нижний предел функции)

У нас есть алгоритм, который можно описать функцией f(n). Итак, чтобы определить BigΩ of f(n)нам нужно найти функцию, скажем, g(n)наиболее подходящая к нижней границе f(n). Это означает, что после определенного значения, n0, значение f(n) всегда будет превышать g(n).

Мы можем записать это как,
f(n)≥ C g(n)
где n≥n0; C>0; n0≥1

Если вышеуказанные условия выполняются, мы можем это сказать g(n) есть BigΩ от f(n), или
f(n) = Ω (g(n))

Можем ли мы заключить, что Ω(…) является дополнительным к O(…)? Переходим к последней главе этой публикации…

Большая Тета (θ)?
ТБольшая тета(θ) является своего рода комбинацией BigO и BigΩ. Это дает нам средний сценарий выполнения алгоритма. Это означает, что это даст нам среднее значение лучшего и худшего случая. Давайте разберем это математически.

1*c1N4K2a264c7Lz5a79HCAA@2x
Bigθ (самый точный нижний и верхний предел функции)

Рассмотрение алгоритма, который можно описать функцией f(n). Большойθ из f(n) будет функцией, скажем, g(n)которая максимально ограничивает его как нижним, так и верхним пределом, так что,
C₁g(n) ≤ f(n)≤ C₂ g(n)
где C₁, C₂ >0, n≥ n0,
n0 ≥ 1

Это означает, что после определенного значения, n0, значение C₁g(n) всегда будет меньше f(n)и значение C₂ g(n) всегда будет превышать f(n).

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

Рассмотрим массив размером, скажем, n, и мы хотим выполнить линейный поиск, чтобы найти элемент x в этом. Предположим, что массив смотрится примерно так в памяти.

1*aQTqrkxiEDXDu-UIMlt51A
Линейный поиск

Исходя из концепции линейного поиска, если x=9, то это будет самый лучший сценарий для следующего случая (поскольку нам не нужно повторять весь массив). И из того, что мы только что узнали, сложность для этого можно записать как Ω(1). Имеет ли смысл?

Подобным образом, если бы x равнялся 14, это был бы худший сценарий, и сложность была бы O(n).

Какова будет средняя сложность дела для этого?
θ(n/2) => 1/2 θ(n) => θ(n) (Поскольку мы игнорируем константы при вычислении асимптотических сложностей).

Итак вот, люди. Фундаментальное понимание сложности алгоритмов. Хорошо ли у вас получилось? Оставляйте свои советы, вопросы, предложения в комментариях ниже. Спасибо за чтение!❤️

Литература: —

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *