O (1): Обычный код без петель. Просто протекает. Поиск в таблице поиска - O (1).
O (log (n)): эффективно оптимизированные алгоритмы. Пример: алгоритмы двоичного дерева и двоичный поиск. Обычно не болит. Вам повезло, если у вас есть такой алгоритм.
O (n): один цикл над данными. Болит за очень большие n.
O (n * log (n)): алгоритм, который выполняет какую-то стратегию разделения и завоевания. Болит за большие п. Типичный пример: merge sort
O (n * n): вложенная петля какого-то типа. Болит даже с небольшим n. Общий с наивными матричными расчетами. Вы хотите избежать такого алгоритма, если сможете.
O (n^x для x> 2): злая конструкция с несколькими вложенными петлями. Болит за очень маленький n.
O (x^n, n! И хуже): freaky (и часто рекурсивные) алгоритмы, которые вы не хотите иметь в производственном коде, за исключением очень контролируемых случаев, для очень маленького n, и если действительно не лучше альтернатива. Время вычисления может взорваться при n = n + 1.
Перемещение вашего алгоритма из класса повышенной сложности может заставить ваш алгоритм летать. Вспомните преобразование Фурье, у которого есть алгоритм O (n * n), который был непригодным для использования с оборудованием 1960-х годов, за исключением редких случаев. Затем Кули и Туки сделали некоторые умные сокращения сложности, повторно используя уже рассчитанные значения. Это привело к широкому внедрению БПФ в обработку сигналов. И, в конце концов, именно поэтому Стив Джобс сделал состояние с iPod.
Простой пример: Наивные программисты C написать этот вид цикла:
for (int cnt=0; cnt < strlen(s) ; cnt++) {
/* some code */
}
Это алгоритм O (N * N) из-за реализации StrLen(). Гнездовые петли приводят к умножению сложностей внутри большого О. O (n) внутри O (n) дает O (n * n). O (n^3) внутри O (n) дает O (n^4). В этом примере предварительная вычисление длины строки немедленно превратит цикл в O (n). Joel has also written about this.
Однако класс сложности - это еще не все. Вы должны следить за размером n. Переработка алгоритма O (n * log (n)) для O (n) не поможет, если количество (теперь линейных) команд растет массово из-за переделки. И если в любом случае n мало, оптимизация тоже не даст большого взрыва.
Одним словом, некоторые люди пишут код, который дерьмо, но не может понять, почему это дерьмо. Обозначение Big-O может помочь помочь им понять, что наряду с обозначением, о котором они не знают, это реальный эффект замедления рабочего времени их кода, который зависит от длины n в этом случае (переменная at runtime), что они не понимают, что код начинается из crappy и становится все хуже и хуже по мере увеличения размера набора данных. – 2010-06-25 12:45:24