Учитывая две функции, является ли одна функция биг-О другой функции?

Question

Мой вопрос касается обозначения big-Oh в алгоритме анализа. Хотя Big-Oh кажется математическим вопросом, он очень полезен при анализе алгоритмов.

Предположим, две функции определены ниже:

• f (n) = 2 (в степени n), когда n чётно
• f (n) = n, если n нечетно
• g (n) = n, когда n чётно
• g (n) = 2 (в степени n), если n нечетно.

Для двух вышеуказанных функций, какая из них большая, а другая? Или не является ли какая-либо функция Big-Oh другой функции.

Спасибо!

Answer 1

В этом случае

• f ∉ O (г) и
• g ∉ O (f).

Это потому, что нетнезависимо от того, какие константы N и k вы выберете,

• существует i ≥ N такое, что f(i)> кг (i) и
• существует j ≥ N , такое что g (j)> kf (j).

Answer 2

Обычно Биг-О и Биг-Тета нотации запутываются.

Попытка непрофессионала в определении может состоять в том, что Биг-О означает, что одна функция растет так быстро илибыстрее , чем другой, т. е. при достаточно большом n, f(n)<=k*g(n), где k - некоторая константа.Это означает, что если f (x) = 2x ^ 3, то оно находится в O (x ^ 3), O (x ^ 4), O (2 ^ x), O (x!) И т. Д.

Big-Theta означает, что одна функция растет так же быстро , как и другая, и ни одна из них не способна «перерасти» другую, или k1*g(n)<=f(n)<=k2*g(n) для некоторых k1 и k2.В терминах программирования это означает, что эти две функции имеют одинаковый уровень сложности.Если f (x) = 2x ^ 3, то это в Θ (x ^ 3), как, например, если k1 = 1 и k2 = 3, 1*x^3 < 2*x^3 < 3*x^3

По моему опыту, когда программистыГоворя о Big-O, на самом деле речь идет о Big-Θ, поскольку нас больше волнует со скоростью часть больше, чем не быстрее часть.

Тем не менее, если две функции с разными Θ объединяются, как в вашем примере, более крупная - (Θ (2 ^ n) - глотает меньшую - Θ (n), поэтому оба f и g имеют одинаковую сложность Big-O и Big-.. В этом случае правильно, что

f(n) = O(g(n)), also f(n) = Θ(g(n))
g(n) = O(f(n)), also g(n) = Θ(f(n))

, так как они имеют одинаковую сложность, они O и Θ связаны друг с другом.

Answer 3

Отношение Биг-О весьма специфично в том смысле, что одна функция после конечного n всегда больше другой.

Это правда здесь? Если это так, дайте такой n. Если нет, вы должны доказать это.