Big -O обозначение

Question

Эй, у меня есть вопрос. скажи t(n) = O(n log(n)) и ты знаешь, что это правда.

а затем вы дали эти заявления и сказали сказать, должны ли они быть истинными или ложными. t(n) = n^4 и t(n) = O(N^4)

Утверждение t(n) = n^4 ложно, а утверждение t(n) = O(N^4) верно. Почему?

Answer 1

Вы должны помнить, что когда вы пишете t(n) = O(n log(n)) и t(n) = O(N^4), на самом деле это означает, что t(n) равно в O(...), а не равно (100 * *)* - это набор функций, и функция не может быть равна набору функций).Однако когда вы пишете f(n) = n^4, это означает, что f(n) равно n^4.

Теперь, если f(n) в O(n log n), оно также в O(n^4), потому что O(n^4)расширенный набор O(n log n).Однако он не может быть равен n^4, поскольку n^4 не находится в O(n log n).

Answer 2

Посмотрите на второе уравнение в это .Из этого уравнения очевидно, что t (n) = n ^ 4 = O (n ^ 4).

t (n) = O (n log n) неверно, поскольку ∀M> 0, x,∃n> x, t (n) = n ^ 4> M (n log n).(если n> log n и n> M, n ^ 4> M * n ^ 3 = M (n * n ^ 2)> M (n * log n) = M (n log n) и n> log nкогда (примерно) n> 5)

Answer 3

Идея записи Big O состоит в том, что она представляет собой абстрактную функцию времени, она фокусируется на самой медленной части вашего алгоритма и игнорирует вещи, которые влияют на время выполнения (т. Е. T (n)), но на самом деле не создает огромныхРазница.

Например, если ваша функция работает с набором элементов размером n и просто просматривает их, выполняя некоторые вычисления, вы бы сказали t (n) = O (n).Скажем, вы выполнили какую-то операцию только над несколькими элементами в соответствии с некоторыми критериями, вы все равно сказали бы, что t (n) = O (n), но фактическое время, затраченное на t (n), не будет напрямую зависеть от n, следовательно, t(n) = nx не будет выполняться.