Простая нотация Big O

Обозначение «большое О» — это математический инструмент, используемый для описания эффективности алгоритма, другими словами, сколько шагов требуется для завершения алгоритма.

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

Такие компании, как Apple, Google и Meta, клянутся Big O, вот почему вы тоже должны:

Работа с большими объемами данных

Вы можете написать два метода сортировки массива: один с большим O из O(n), а другой с большим O из O(n²). Но если они делают то же самое, какое значение имеет Big O? Ну, допустим, длина массива равна 3. Это означает, что алгоритм O(n) займет 3 шага, а O(n²) — 9 шагов. Допустим, каждый шаг занимает 2 мс, это означает, что O(n) занимает 6 мс, а O(n²) — 18 мс. Маловероятно, что вы заметите эту разницу, если создаете приложение, не требующее высокой производительности. Однако, скажем, Google хочет использовать те же алгоритмы, внезапно Big O становится намного более важным, поскольку они имеют дело с огромными объемами данных. Если бы массив Google содержал 10 000 элементов, то потребовалось бы 10 000 шагов, чтобы отсортировать его за O(n) (2,7 часа) или 100 000 000 (сто миллионов) при O(n²) (55,6 дня).

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

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

Время и место

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

Вот некоторые распространенные среды выполнения Big O:

  • O(n) — необходимое количество шагов равно количеству элементов, с которыми вы имеете дело.
  • O(1) — необходимое количество шагов постоянно и не зависит от количества элементов, с которыми вы имеете дело.
  • O(Logn) — необходимое количество шагов равно Log n.
  • O(nLogn) — Требуемое количество шагов равно n x (Log n)
  • O(2^n) — количество необходимых шагов увеличивается как степень двойки, где n — показатель степени
  • O(n!) — количество требуемых шагов увеличивается факторным образом.

Лучший, средний и худший случай

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

Если мы хотим выполнить линейный поиск, наихудшим случаем будет O(n), что будет означать, что цель находится в последнем элементе списка. Лучшим случаем для линейного поиска будет O(1), т. е. постоянное время, то есть первый проверенный элемент будет содержать цель. Таким образом, средний случай будет O(n/2), что означает, что элемент присутствует в центре списка.

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

Выбор алгоритмов и компромиссы

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

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