Простыми словами о Big O (Time Complexity)

Есть у программистов понятие «временная сложность» (time complexity or Big O) для сравнительной оценки эффективности алгоритма.

К примеру, для некоторой структуры может быть линейное время доступа (искомый элемент либо встретится сразу, либо он может быть в самом конце, и если структура очень большая (n — это число элементов), а элемент в самом конце, то поиск может быть долгим. Обычно рассматривают время доступа в среднем и худшем случае. Big O — обозначение верхней границы, т.е. худшего случая. Для нашего примера O(n).

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

Так вот, поездка на машине в снежную погоду — это скорее O(n) (неизвестно за сколько доберёшься из-за пробок), а на метро — O(1) (всегда примерно одинаковое время на дорогу).

Эффективность алгоритмов варьируется от O(1) до O(n!), их полный список можно найти на вики (ссылка в конце статьи).

В своё время мне помогли «войти в тему» следующие статьи, их я очень советую прочесть:

  • Знай сложности алгоритмов — Краткая шпаргалка по сложности алгоритмов. Теперь вам будет проще выбрать наиболее эффективный тип данных и алгоритм, подходящий под ваши задачи.
  • Введение в анализ сложности алгоритмов — Лёгкий для чтения и понимания материал. Идеально, чтобы начать разбираться во всех этих алгоритмах и «читать» их сложность. Обязательно прочтите все части.
  • Big O notation — Orders of common functions — не пугайтесь длинного списка, просто запомните что сложность от O(1) до O(n) норм, а всё что больше — уже не норм.

No Comments.

Leave a Reply

(required)

(required)