что делает O (N) средний [дубликат]

45
задан Community 23 May 2017 в 11:54
поделиться

8 ответов

Комментарий относился к нотации Big-O .

Вкратце:

  1. O (1) означает в постоянном времени - независимо от количества элементов.
  2. O (N) означает пропорционально количество элементов.
  3. O (log N) означает время, пропорциональное log (N)

Обычно любая нотация «O» означает, что операция займет время до k * f (N)
где:

k - постоянный множитель

f () - функция, которая зависит от N

58
ответ дан 26 November 2019 в 20:58
поделиться

Это называется 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/

23
ответ дан 26 November 2019 в 20:58
поделиться

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) неплохо для вставки, но не самый быстрый.

15
ответ дан 26 November 2019 в 20:58
поделиться

В частности, 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, это то, что ваша функция не медленнее, чем это, но на самом деле никто не сказал бы это, кроме как доказать точку, потому что это не очень полезная и вводящая в заблуждение информация, несмотря на ее техническую точность.

11
ответ дан 26 November 2019 в 20:58
поделиться

Краткий ответ: это означает, что время обработки находится в линейной зависимости от размера ввода. Например, если размер ввода (длина списка) утроится, время обработки (примерно) утроится. И если оно увеличивается в тысячу раз, время обработки также увеличивается в той же степени.

Подробный ответ: см. Ссылки, предоставленные Яном Пи и dreeves

4
ответ дан 26 November 2019 в 20:58
поделиться

Относится к тому, насколько сложна ваша программа, т. Е. Сколько операций требуется для реального решения проблемы. O (n) означает, что каждая операция требует того же количества шагов, что и элементы в вашем списке, что для вставки выполняется очень медленно. Аналогичным образом, если у вас есть O (n ^ 2), означает, что любая операция требует «n» квадратов шагов для выполнения и так далее ... «O» означает порядок величины, а выражение в скобках - всегда связано с количеством элементов, которыми управляют в процедуре.

6
ответ дан 26 November 2019 в 20:58
поделиться

Википедия объясняет это намного лучше, чем я могу, однако это означает, что если размер вашего списка равен N, для вставки элемента требуется максимум N циклов / итераций. (Фактически, вам придется перебирать весь список)

Если вы хотите лучше понять, есть бесплатная книга из Беркли , в которой более подробно рассматриваются обозначения.

2
ответ дан 26 November 2019 в 20:58
поделиться

Это может помочь:

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

O (n): поиск элемента в несортированном список или искаженное дерево (худший случай); сложение двух n-значных чисел

Удачи!

3
ответ дан 26 November 2019 в 20:58
поделиться
Другие вопросы по тегам:

Похожие вопросы: