Число в круглых скобках - это количество операций, которые вы должны выполнить для фактического выполнения операции, всегда выраженное как функция от количества элементов, с которыми вы имеете дело. Вы никогда не беспокоитесь о том, насколько сложны эти операции, а только об их общем количестве.
Если массив заполнен и его размер необходимо изменить, вам необходимо скопировать все элементы в новый массив. Одна операция для каждого элемента в массиве, таким образом, время выполнения O (n). Однако в большинстве случаев вы выполняете только одну операцию для среды выполнения O (1).
Общие значения:
O (1): только одна операция, например добавление ее в list, когда список не полон.
O (log n): Обычно это происходит, когда у вас есть двоичный поиск или что-то подобное, чтобы найти вашу цель. Обратите внимание, что основание журнала не указывается, поскольку разница является просто константой, и вы всегда игнорируете константы.
O (n): одна операция для каждого элемента в вашем наборе данных. Например, несортированный поиск.
O (n log n): обычно встречается в хороших процедурах сортировки, где вам нужно обрабатывать каждый элемент, но вы можете разделять и побеждать, как вы go.
O (n ^ 2): Обычно встречается, когда вы должны учитывать каждое взаимодействие двух элементов в вашем наборе данных и не иметь возможности его организовать. Например, я написал длинный go, чтобы найти почти повторяющиеся изображения. (Точные дубликаты можно обработать, составив словарь хэшей и проверив, существует ли ha sh и, следовательно, O (n) - два прохода являются константой и отбрасываются, вы бы не сказали O (2n).)
O (n ^ 3): К тому времени, как вы достигнете этого кайфа, вы очень внимательно обдумаете это. Теперь вы смотрите на трехстороннее взаимодействие элементов в вашем наборе данных.
Могут существовать более высокие порядки, но вам нужно тщательно обдумать, что они будут делать. Я отправил производственный код, который был O (n ^ 8), но с очень тяжелым обрезанием путей, и даже тогда для его выполнения потребовалось 12 часов. Если бы природа данных не способствовала такой обрезке, я бы вообще не написал ее - код все равно работал бы.
Иногда вы сталкиваетесь с еще более неприятными вещами, которые требуют тщательного рассмотрения того, является ли он будет терпимо или нет. Для больших наборов данных это невозможно:
O (2 ^ n): Пример из реальной жизни: попытка сократить пути, чтобы сохранить минимальное остовное дерево - я вычислил все возможные деревья и оставил самые дешевые. Несколько экспериментов показали, что n никогда не превышает 10, я думал, что все в порядке - до тех пор, пока другое начальное число не дало n = 22. Я переписал процедуру для получения не всегда идеального ответа, который вместо этого был O (n ^ 2).
О (п!): Я не знаю примеров. Он взрывается ужасно быстро.