Возможный дубликат:
Что такое примечание Big O? Вы используете его?
Привет всем,
довольно базовый вопрос о нотации масштабируемости.
Недавно я получил комментарий к сообщению о том, что мой python order-list implimentation "но будьте осторожны, что ваша реализация" упорядоченного набора "- это O (N) для вставок"
Это здорово знать, но я не уверен, что это значит.
Я видел обозначения, такие как n (o) o (N), N (o-1) или N (o * o)
к чему относится обозначение выше?
Комментарий ссылался на примечание Big-O.
Коротко:
В принципе любая нотация "O" означает, что операция займет время до максимума k * f (N)
где:
k - постоянный множитель
f() - функция, зависящая от N
Он называется Big O Notation: http://en.wikipedia.org/wiki/Big_O_notation
Так что, говоря, что вставка O(n) означает, что вам нужно пройти через весь список (или половина его - большая нотация O игнорирует постоянные факторы) для выполнения вставки.
Это выглядит как приятное введение: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
В частности, O (n) означает, что если в списке должно быть как можно больше элементов, это займет не более не более, если в 50 раз больше будет Не более в 50 раз. См. Статью, содержащуюся в википедии, трижды указана для более подробной информации.
Изменить (выделено полужирным шрифтом): было указано, что Big-O представляет верхнюю границу, поэтому, если в списке будет в два раза больше элементов, вставка займет не более двух раз, а если их 50 раз многие элементы, это займет не более 50 раз.
Если бы это было дополнительно Q (n) (Big Omega of n), то для списка, который в два раза больше, потребуется как минимум вдвое больше. Если ваша реализация - это как O (n), так и Ω (n), что означает, что она займет как минимум, так и не более двух раз, чтобы список был вдвое большим, тогда можно сказать, что это Θ (n) (Big Theta of n), а это означает, что в два раза больше, чем в два раза.
Согласно Википедии (и личный опыт, будучи виновным в этом сам) Big-O часто используется там, где подразумевается Big-Theta. Было бы технически корректным называть вашу функцию O (n ^ n ^ n ^ n), потому что все Big-O говорит, что ваша функция не медленнее, но никто на самом деле не сказал бы, кроме как доказать точку, потому что она не очень полезная и вводящая в заблуждение информация, несмотря на то, что она технически точна.
O (n) Big O Notation и относится к сложности данного алгоритма. n относится к размеру ввода, в вашем случае это количество элементов в вашем списке.
O (n) означает, что ваш алгоритм будет выполнять порядок n операций для вставки элемента. например циклическое перемещение по списку один раз (или постоянное число раз, например, дважды или только переключение по половине).
O (1) означает, что он принимает постоянное время, что он не зависит от количества элементов в списке.
O (n ^ 2) означает, что для каждой вставки выполняется n * n операций. т.е. 1 операция для 1 объекта, 4 операции для 2 элементов, 9 операций для 3 предметов. Как вы можете видеть, алгоритмы O (n ^ 2) становятся неэффективными для обработки большого количества элементов.
Для списков O (n) неплохо для вставки, но не самый быстрый. Также отметим, что O (n/2) считается как O (n), потому что оба они растут с одинаковой скоростью с n.
Короткий ответ: это означает, что время обработки находится в линейном отношении к размеру ввода. Например, если размер ввода (длина списка) троек, время обработки (примерно) утроится. И если он увеличивается в тысячу раз, время обработки также увеличивается с одинаковой величиной.
Длинный ответ: см. ссылки, предоставленные Ian P и dreeves
Это относится к тому, насколько сложна ваша программа, т.е. сколько операций требуется для фактического решения проблемы. O (n) означает, что каждая операция занимает столько же шагов, сколько и элементы в вашем списке, которые для вставки очень медленные. Точно так же, если у вас есть O (n ^ 2), означает, что любая операция принимает "n" квадрат числа шагов для выполнения и т.д. "O" - для порядка величины, а выражение в круглых скобках всегда связано с количеством обрабатываемых элементов в процедуре.
Это может помочь:
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
O (n): поиск элемента в несортированном список или неправильное дерево (наихудший случай); добавление двух n-значных чисел
Удачи!
Википедия объясняет, что это намного лучше, чем я могу, однако это означает, что если ваш размер списка равен N, он принимает максимум N циклов/итерации для вставки элемента. (По сути, вам нужно перебирать весь список)
Если вы хотите лучшего понимания, есть бесплатная книга из Беркли, которая более подробно описывает обозначения.