Почему обозначение Big O для исполнения с постоянным временем O (1) вместо O (2)?

Question

Я понимаю, что O (1) указывает, что алгоритм будет занимать постоянное количество времени выполнения независимо от входных измерений. Я также понимаю, что O (N) указывает на линейное увеличение времени выполнения, пропорциональное размеру входного измерения.

Однако я знаю это только из-за запоминания их определений. У меня нет интуиции в интерпретации O (1), и я просто вспоминаю, что это означает постоянное время выполнения. Мне любопытно, как я могу понять интуицию при чтении больших O-нотаций.

Так что для выполнения с постоянным временем O (1), что представляет 1? Почему бы не иметь O (2)? 2 также является константой, которая не зависит от размера ввода N.

Answer 1

Обозначение O(...) означает набор функций. Грубо говоря, O(f(n)) - это набор функций, которые не растут асимптотически быстрее, чем f.

Функция константы f(n) = 1 вообще не растет, равно как и функция константы f(n) = 2, поэтому ни один из них не растет асимптотически быстрее, чем другой. Кроме того, любая другая функция растет асимптотически быстрее, чем 1, если и только если она растет асимптотически быстрее, чем 2. Таким образом, функция находится в наборе O(1) тогда и только тогда, когда она находится в наборе O(2), что означает, что они являются одним и тем же набором.

Это означает, что вы можете написать O(2), и это строго правильно, но проще (и, следовательно, условно) написать O(1). Вы можете думать об этом немного как о решении математической задачи, где ответ - дробь; вы должны написать ответ в его простейшей форме. Строго говоря, 6/4 равно 3/2, но обычно пишется 3/2.

Answer 2

Потому что, когда вы оцениваете сложность функции, для вас важны переменные. Если вы находите какую-либо константу, вы ее откладываете.

Например:

for(int i = 0; i < 2 * N; i++){ print("Hello"); }

Ваша сложность равна O (2N), но поскольку для вас важны переменные, вы берете константы вне уравнения, оставляя O (N).

Теперь предположим, что это:

int a = b + c + d;

Сложность, очевидно, постоянна, но количество операций не только 1, скажем, это 3 (2 операции и 1 атрибуция). Тогда у вас есть O (3). Можно смело сказать, что O (3) = O (3 * N ^ 0). Мы следуем той же процедуре вырезания констант, оставляя нас с O (N ^ 0) = O (1).

Просто чтобы уточнить, когда мы оцениваем сложности, мы представляем, что переменная будет принимать очень большие значения, такие большие значения, что любая умножающая константа не будет иметь значения, когда переменная становится бесконечной, поэтому мы откладываем ее. То же самое верно для аддитивных постоянных, например, O (5N + 3) = O (N).

Answer 3

Вы можете использовать O(2), так же, как вы можете использовать O(33652 n²- log n).

С риском казаться странным.