Хотя я понимаю концепцию как сложности алгоритмов, так и логарифмической сложности в программировании, я не знаю, как определить сложность логарифма который включает переменные разных степеней.Сложность алгоритма: log (x^2 + x^3) = O (?)
Вот некоторые примеры:
log(x^2 + 3x^3) = O(?)
log(x^3 + 5) = O(?)
Любая помощь будет очень ценится.
спасибо.
O(log(x))
Просто из-математического правила, log(xk) = k⋅log(x) (это строго из определения бревна)
Кроме того, мы знаем, что O является асимптотической мультипликативной нотации, поэтому умножение на константу не влияет на это.
Доказательство:
log(x² + 3x³) ≤ log(4x³) ≤ log(x⁴) для достаточно большого х
Так log(x²+3x³) ≤ log(4x³) ≤ log(x⁴) = 4⋅log(x), который мы знаем, O (журнал (х)) по определению
Это доказательство верхней O связаны
С другой стороны (Показать Тета, которая не нужна, но вас может заинтересовать)
log(x²+3x³) ≥ log(x²) >= 2⋅log(x), который является O (log (x)) по определению
Это именно то, что мне было нужно. Большое вам спасибо! – netcentric