Умножение временной сложности?

Question

Я понимаю, что при умножении двух временных сложностей вы просто умножаете их как обычно, например, сложность времени n log n, умноженная на временную сложность n, даст вам временную сложность (n^2) log n.

Но где же границы вступают в игру? Итак, если n log n была верхней границей, а n также была верхней границей, какая из них была бы продуктом? И что было бы для других комбинаций нижней границы верхней границы и плотно связанной? (Например, верхняя граница х плотно связана, верхняя граница х снижена и плотно привязана к нижней границе.)

Спасибо за любую помощь.

Answer 1

Так что если п лог п была верхняя граница и п была верхняя граница тоже, какая из них была бы продуктом?

Верхняя граница. См. Любой хороший ответ учебника для формального анализа; интуитивный смысл умножения этих двух верхних границ является «если вы должны сделать максимум п LG п операции стоимости в наиболее п каждый, то вы выполняете в большинстве п ² Lg п работы» ,

UpperBound × тесно связаны

Плотный связан одновременно верхняя граница и нижняя граница, так что это есть верхняя граница.

тесно связаны × LowerBound

... и теми же рассуждениями, это нижняя граница.

UpperBound × LowerBound

Нет общего правила. Предположим, что вы выполнили по крайней мере n ² операции не более n раз. Это может быть совсем не работа, или экспоненциальная сумма, или что-то большее.

Answer 2

Это чисто математический вопрос:

f(x) является O(g(x)) тогда и только тогда, когда существует M, x0 такое, что для всех |f(x)| <= M*|g(x)|x > x0. Вы увидите это в большинстве книг по элементарной сложности.

Предположим, f(x) является O(F(x)) и g(x) является O(G(x)). Затем |f(x)| <= M_f * |F(x)| для всех x > x0F и |g(x)| <= M_g * |G(x)| для всех x > x0G.

|f(x) * g(x)| = |f(x)| * |g(x)| <= M_f * M_g * |F(x)| * |G(x)| для всех x > max(x0F, x0G) так f(x) * g(x) является O(F(x) * G(x)) и сложности действительно размножаются (Write M = M_f * M_g и x0 = max(x0f, x0g) применяется к определению большого-O)