Большой О для постоянной сложности времени

Question

Если у меня постоянная временная сложность, например, c1 + c2 + c3, тогда я знаю, что это займет линейное время.Я хочу выразить это в терминах больших цифр.Если сложность по времени равна f (n) = 2n + 3, тогда мы пишем O (n), а затем докажем, что f (n)

Answer 1

Если вы знаете, что временная сложность алгоритма представляет собой комбинацию некоторых констант, таких как c1 + c2 + c3, то вы можете определить функцию f (x) = c1 + c2 + c3 = c. Затем, используя определение большого O, который является

f (x) = O (g (x)) при переходе x в бесконечность

тогда и только тогда, когда существует положительное действительное число M и действительное число x0, такое что

| е (х) | <= Mg (x) для всех x> = x0

мы можем сказать, что f (x) = c - это O (1) с g (x) = 1. Причина в том, что мы можем выполнить требования вышеприведенного определения, выбрав M как константу c, а x0 не ' Здесь значение не имеет, поскольку сложность времени не зависит от значения x.

Answer 2

Постоянная сложность по времени составляет O (1).