Большая сложность времени O

Question

У меня есть временная сложность T (n) = 6n + xn и, по-видимому, сложность Big O (n^2), но я думал, что это будет (n). Я хотел бы понять, почему это (n^2).

Answer 1

Т (п) = O (г (п)) в информатике означает этот

Итак, очевидно, ваш Т (п) функция принадлежит множеству O (N^2)

Но главный вопрос в том, что ваш «х» в T (n) зависит от ввода n?

Если ответ да, то очевидно, что Т (п) = О (п) + х принадлежит множеству O (N^2)

Если ответ нет и х просто постоянный множитель, а то T (n), конечно, принадлежит также O (n^2) (свободный верхний предел). Но более жесткая верхняя граница T (n) принадлежит O (n), поскольку T (n) = O (n) + O (n), что только O (n)

Потому что мы говорим о верхних границах (большая O-запись), правильно сказать, что функция O (n) принадлежит также множеству O (n^2). Если нас интересует только то, что наш алгоритм делает даже в худшем случае в O (n^2) время.

Надеюсь, что это поможет