Сложность алгоритма и нотация Big O

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

Разным алгоритмам для решения одной и той же проблемы и одних и тех же входных данных требуется разное время для решения проблемы.

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

Эта сложность называетсяБольшой O, по той причине, что мы используем верхний регистрoписьмо как условность:O(n),O(1)и так далее.

Самые популярные меры Big O, отсортированные от более эффективных к менее эффективным, следующие:

  • O(1)
  • O(log n)
  • O(n)
  • O(n * log n)
  • O(n^2)
  • O(n!)

кудаnколичество входов. Например, если вам нужно отсортировать 2 элементаnравно 2, и если вам нужно отсортировать 20 000 элементов,nсоставляет 20,000.

Но подставлять значение вO()расчет. Это символ, призванный сигнализировать разработчикам и всем, кто смотрит на алгоритмы, о его эффективности.

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

Алгоритм сO(n)напольные весылинейнос количеством входов. Если для 10 элементов требуется 1 секунда, для 100 элементов потребуется 10 секунд.

Алгоритм сO(n^2), если с 4 элементами занимает 16 секунд, то с 10 элементами занимает 100 секунд.

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

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

Но когда у алгоритмов разные классы (O(n)противO(n^2)например), в этом нет никаких сомнений.