Комментарий относился к нотации 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) - это нотация Big O и относится к сложности данного алгоритма. n относится к размеру ввода, в вашем случае это количество элементов в вашем списке.
O (n) означает, что ваш алгоритм примет порядок из n операций для вставки элемента. например, просмотр списка один раз (или постоянное количество раз, например, дважды или только половину цикла).
O (1) означает, что это занимает постоянное время, что не зависит от количества элементов в списке.
O (n ^ 2) означает, что для каждой вставки требуется n * n операций. т.е. 1 операция для 1 элемента, 4 операции для 2 элементов, 9 операций для 3 элементов. Как видите, алгоритмы O (n ^ 2) становятся неэффективными для обработки большого количества элементов.
Для списков O (n) неплохо для вставки, но не самый быстрый.
В частности, O (n) означает, что если в списке вдвое больше элементов, потребуется Не более в два раза дольше, если их в 50 раз больше это займет Не более чем в 50 раз дольше. См. Статью в Википедии, на которую указывает dreeves, для получения более подробной информации
Изменить (выделено жирным шрифтом выше): было указано, что Big-O действительно представляет верхнюю границу, поэтому, если в списке вдвое больше элементов, вставка займет максимум вдвое длиннее, а если элементов в 50 раз больше, это займет максимум в 50 раз больше.
Если бы это было дополнительно Ω (n) (Большая Омега из n), то для списка, который в два раза больше, потребовалось бы минимум в два раза больше. Если ваша реализация одновременно O (n) и Ω (n), это означает, что Я возьму как минимум , так и максимум вдвое больше для списка вдвое большего размера, тогда можно сказать, что это будет Θ (n) (большая тета из n), что означает, что это займет ровно в два раза больше времени, если будет вдвое больше элементов.
Согласно Википедии (и личному опыту, будучи виноватым в этом я сам) Big-O часто используется там, где имеется в виду Big-Theta. Было бы технически правильно вызвать вашу функцию O (n ^ n ^ n ^ n), потому что все, что говорит Big-O, это то, что ваша функция не медленнее, чем это, но на самом деле никто не сказал бы это, кроме как доказать точку, потому что это не очень полезная и вводящая в заблуждение информация, несмотря на ее техническую точность.
это займет ровно в два раза больше времени, если элементов будет вдвое больше.Согласно Википедии (и личному опыту, будучи виноватым в этом я сам) Big-O часто используется там, где имеется в виду Big-Theta. Было бы технически правильно вызвать вашу функцию O (n ^ n ^ n ^ n), потому что все, что говорит Big-O, это то, что ваша функция не медленнее, чем это, но на самом деле никто не сказал бы это, кроме как доказать точку, потому что это не очень полезная и вводящая в заблуждение информация, несмотря на ее техническую точность.
это займет ровно в два раза больше времени, если элементов будет вдвое больше.Согласно Википедии (и личному опыту, будучи виноватым в этом я сам) Big-O часто используется там, где имеется в виду Big-Theta. Было бы технически правильно вызвать вашу функцию O (n ^ n ^ n ^ n), потому что все, что говорит Big-O, это то, что ваша функция не медленнее, чем это, но на самом деле никто не сказал бы это, кроме как доказать точку, потому что это не очень полезная и вводящая в заблуждение информация, несмотря на ее техническую точность.
Краткий ответ: это означает, что время обработки находится в линейной зависимости от размера ввода. Например, если размер ввода (длина списка) утроится, время обработки (примерно) утроится. И если оно увеличивается в тысячу раз, время обработки также увеличивается в той же степени.
Подробный ответ: см. Ссылки, предоставленные Яном Пи и dreeves
Относится к тому, насколько сложна ваша программа, т. Е. Сколько операций требуется для реального решения проблемы. O (n) означает, что каждая операция требует того же количества шагов, что и элементы в вашем списке, что для вставки выполняется очень медленно. Аналогичным образом, если у вас есть O (n ^ 2), означает, что любая операция требует «n» квадратов шагов для выполнения и так далее ... «O» означает порядок величины, а выражение в скобках - всегда связано с количеством элементов, которыми управляют в процедуре.
Википедия объясняет это намного лучше, чем я могу, однако это означает, что если размер вашего списка равен N, для вставки элемента требуется максимум N циклов / итераций. (Фактически, вам придется перебирать весь список)
Если вы хотите лучше понять, есть бесплатная книга из Беркли , в которой более подробно рассматриваются обозначения.
Это может помочь:
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
O (n): поиск элемента в несортированном список или искаженное дерево (худший случай); сложение двух n-значных чисел
Удачи!