Возможно ли когда-нибудь, чтобы Big O было меньше O (1)?[дубликат]

Question

Возможный дубликат:
существуют ли алгоритмы O (1/n)?

Возможно ли, чтобы ваш код был большим O меньше O (1)?

Answer 1

O(1) просто означает операцию с постоянным временем.Это время может составлять 1 наносекунду или 1 миллион лет, эта запись не является мерой абсолютного времени.Если, конечно, вы не работаете над ОС для машины времени, то, возможно, ваша функция DoTimeTravel() будет иметь сложность O(-1) :-)

Answer 2

Не совсем. O(1) это постоянное время.Выражаете ли вы это как O(1) или O(2) или O(.5) на самом деле не имеет большого значения, если говорить о чисто большом обозначении O.

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

Answer 3

Единственное, что займет меньше O(1) (постоянное время), — это операция, которая абсолютно ничего не делает и, следовательно, занимает нулевое время.Но даже NOP обычно занимает фиксированное количество циклов...