Хотя я понимаю концепцию как сложности алгоритмов, так и логарифмической сложности в программировании, я не знаю, как определить сложность логарифма, включающего переменные разных степеней.
Вот некоторые примеры:
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⁴) для достаточно большого x
Итак, log(x²+3x³) ≤ log(4x³) ≤ log(x⁴) = 4⋅log(x), который, как мы знаем, равен O(log(x)) по определению.
Это доказательство верхней границы O
В другом направлении (Показ Theta, который не нужен, но может вас заинтересовать)
log(x²+3x³) ≥ log(x²) >= 2⋅log(x), что по определению равно O(log(x))
