STL производительность O (ln (n)) вопросы

Question

Пожалуйста, может кто-нибудь объяснить это:

Если в документации сказано, что STL std :: vector скорость поиска элемента = O (ln (n)), что это значит.

O(ln(n)) - что такое " O ", где я могу прочитать об этом?

И где я могу прочитать о производительности других контейнеров STL

Большое спасибо

Answer 1

Big O нотация - это способ измерения масштабирования алгоритма по мере роста размера данных, над которыми он работает.

Поиск элемента, если вектор обычно O(n), это только O(lg(n)), когда вектор отсортирован, и вы используете один из алгоритмов двоичного поиска .

Сложность каждого алгоритма указана в стандарте, а также влюбая ссылка (например, указанная выше ссылка на std::lower_bound).

Кстати, ln равна log на основе e, но все логарифмы имеют одинаковую сложность, поэтому даже при выполнении двоичного поискаlg (log ₂ ) технически правильно сказать, что это O(ln(n)).

Answer 2

Это известно как нотация Big O , это выражение асимптотической сложности данного алгоритма и в отношении некоторых параметров.

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

Например, в случае бинарного поиска мы выражаем связь между количеством выполненных сравнений в зависимости от размера набора, в котором мы ищем.

Из этого обычно можно определить время выполнения, но это не всегда верно, особенно если не выбрана правильная «операция» в отношении реализации или аппаратных ограничений.

Несколько дней назад был хороший пост, в котором говорилось о сортировке с использованием ленты в качестве хранилища. Поскольку сложности в поиске выражают количество сравнений и использование ленты в качестве хранилища, время выполнения ленты в основном зависит от движения ленты ... оказалось, что пузырьковая сортировка будет работать лучше, чем быстрая сортировка, несмотря на то, что в целом она описывается как медленная. *

Answer 3

O - big O нотация . Он описывает сложность алгоритма во время выполнения. По сути это количество операций, необходимых для вычисления ответа.

Answer 4

Нотация Big-O о временной сложности выполнения программ.

поэтому O (ln (n)) означает, что доступ к элементам в std :: vector при увеличении вектора пропорционален ln (size_of_vector), но это только для отсортированного вектора с использованием бинарного поиска. Бинарный поиск выполняется быстрее, чем линейный, потому что вы удаляете возможные элементы в два раза быстрее, таким образом, ln на самом деле является базой данных 2.

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

Answer 5

Все остальные ответы прояснились O , чтобы найти типичную сложность данного алгоритма, посмотрите на достойную ссылку, например this . В нижней части каждого алгоритма описана сложность алгоритма.

Answer 6

O - сокращение от «Заказ».Это мера времени выполнения операции.

Например, этот код O (n ^ 2), потому что он будет выполняться n * n раз.

int n = 100;
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
  }
}