Я только что узнал сегодня, что это отношение не выполняется, поскольку изменения журналаЕсли f (n) = O (g (n)), то log (f (n)) = O (log (g (n))?
А также, если f (n) = Θ (g (n)), будет log (f (n)) = Θ (log (г (п)) справедливы?
Любая помощь приветствуется. Спасибо заранее.
Теперь комментарии показали, что этот вопрос об асимптотических пределах, а не о алгоритмической сложности .....
Вы может использовать правило L'Hôpital (информация содержится в любом базовом тексте по дифференциальному исчислению) и тот факт, что производная от ln(x) (натуральный логарифм) равна 1/x, чтобы показать, что асимптотический предел f(n)/g(n) равен асимптотическому пределу log(f(n))/log(g(n)).
Обратите внимание, что это мало или ничего общего с алгоритмической сложностью.
Как вы думаете, сложна ли функция 'log()'? – Peter
log() значительно уменьшит значение, возвращаемое f (n) и g (n). Итак, что не так с log (f (n)) = O (log (g (n)))? Он также должен сохраняться, так как при любой стоимости log (g (n))> log (f (n))! – lU5er
Я думаю, что мы должны уточнить, вы говорите о временной сложности для вычисления функции (которая является контекстом, в котором нотация Big O часто используется в информатике), или вы говорите о предельном поведении самой функции? –