1

私はアルゴリズム試験の勉強をしていますが、練習問題の1つは少し混乱しています。lognがΩ（log（logn））であることを証明することになっています。私はこれを行う2つの方法を知っています：Ωの定義を使用する（すべてのc>=Cに対してlogn>=c * log（logn）となるような定数Cを見つける）、または限界比較を使用する（limをnとして取る） -> logn / log（logn）のinfであり、無限大に等しいことを示します）。私の問題は、最初の方法の定数を見つける方法が本当にわからないことです。2番目の方法では、その制限を評価する方法がわかりません。任意のヒント？ありがとう！

4

2 に答える 2

2

商 f(x)/g(x) の極限を x->infinity として見つけたい場合、f(x) と g(x) も無限大になる場合、通常のアプローチは、L'Hôpitalを適用してみることです。 f(x) と g(x) の導関数を取り、f'(x)/g'(x) の極限を x->無限大として求める規則。

于 2012-10-08T00:02:32.773 に答える
0

c=1を選択するだけです。

log n >= log (log n)

これを使用x >= log xすると、はによって暗示され2^y >= yます。

于 2012-10-08T23:04:16.673 に答える