我目前正在学习算法的期末考试。这不是家庭作业问题,而是来自旧的期末考试。
Show that f(n) = 4logn + log log n is big theta of logn.
很明显,log log n 比 log n 小很多,因此微不足道。但是我怎样才能正式地展示它呢?我熟悉限制和 L'hopital,所以如果您能告诉我如何使用这种方法,我将不胜感激。
我目前正在学习算法的期末考试。这不是家庭作业问题,而是来自旧的期末考试。
Show that f(n) = 4logn + log log n is big theta of logn.
很明显,log log n 比 log n 小很多,因此微不足道。但是我怎样才能正式地展示它呢?我熟悉限制和 L'hopital,所以如果您能告诉我如何使用这种方法,我将不胜感激。
记住大θ的定义。一个函数f(x)
在Theta(g(x))
if
你有f(x) = 4*log(x) + log(log(x))
和g(x) = log(x)
。现在我们必须证明存在c_0
,c_1
并且x_0
满足条件的值。
如果我们取c_0 = 1
并且x_0
足够大log(log(x_0)) > 0
(确切的数字取决于你的对数的底,但总是有这样一个数字,我们并不需要知道它),那么很容易证明第一个不等式是对所有人都为真x > x_0
:(log(x) <= 4*log(x) + log(log(x))
提示:log(log(x))
已经是> 0
并且对数函数是单调递增的。
现在让我们选择c_1 = 5
。第二个不等式现在变为4*log(x) + log(log(x)) <= 5*log(x)
,它简化为
log(log(x)) <= log(x)
对于所有人x > x_0
。我会把这个证明留给你作为练习。:-)
找到 c1 , c2 和 no 的简单方法。
寻找上限:
f(n) = 4logn+loglogn
For all sufficience value of n>=2
4logn <= 4 logn
loglogn <= logn
Thus ,
f(n) = 4logn+loglogn <= 4logn+logn
<= 5logn
= O(logn) // where c1 can be 5 and n0 =2
寻找下限:
f(n) = 4logn+loglogn
For all sufficience value of n>=2
f(n) = 4logn+loglogn >= logn
Thus, f(n) = Ω(logn) // where c2 can be 1 and n0=2
so ,
f(n) = Ɵ(logn)