Блог

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

T(n)= O(g (n)) в информатике означает это

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

Но главный вопрос в том, зависит ли ваш ‘x’ в T (n) от ввода n?

Если ответ положительный, то очевидно, что T(n)=O(n) xn принадлежит множеству O(n ^ 2)

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

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

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