我正在为算法考试而学习，其中一个练习题让我有点困惑。我应该证明 logn 在 Ω(log(logn)) 中。我知道解决这个问题的两种方法：要么使用 Ω 的定义（找到一些常数 C，使得所有 c>=C 的 logn >= c * log(logn)），或者使用极限比较（将 lim 作为 n ->inf of logn/log(logn) 并显示它等于无穷大）。我的问题是我真的不知道如何为第一种方法找到一个常数，而对于第二种方法，我不知道如何评估该限制。有小费吗？谢谢！
问问题
192 次
2 回答
2
如果您想找到商 f(x)/g(x) 的极限为 x->infinity，其中 f(x) 和 g(x) 也趋于无穷大，通常的方法是尝试应用L'Hôpital's 通过取 f(x) 和 g(x) 的导数并找到 f'(x)/g'(x) 的极限作为 x->infinity 来进行规则。
于 2012-10-08T00:02:32.773 回答
0
只需选择 c = 1。
log n >= log (log n)
使用x >= log xwhich 又由2^y >= y.
于 2012-10-08T23:04:16.673 回答