n≠Θ（logn）ですか？

質問は、確認する方法を理解する/理解することを求められます漸近式Θ表記。宿題に関する質問。私はそれを示すことですn≠Θ（logn）n≠Θ（logn）ですか？

解決策：はい、n≠Θ（logn）です。

c1logn ≤ n ≤ c2logn => c2≥n/logn, Ɐ n≥n0 - Impossible

なぜc2≥n/lognを使用できないのですか？

出典

2017-06-09 Dhiraj Aggarwal

[cs.se]または[math.se]についてですので、この質問を議論の対象外とすることにしました。 – Dukeling

@Dukelingあなたはオフトピックを言うとき、それはどういう意味ですか？ –

["off-topic"]（https://stackoverflow.com/help/on-topic）私は質問が[so]には不適切で、別のサイトに適していることを意味します。しかし、[複数のサイトに投稿しないでください]（https://meta.stackexchange.com/questions/64068/is-cross-posting-a-question-on-multiple-stack-exchange-sites-permitted-if-あなたがすでに満足のいく回答を得ているなら、他の人に将来の価値がたくさんあるかもしれないと思う場合を除いて、おそらく（削除して）削除したりマイグレーションしたりしないでください。いくつかの時間の複雑さの問題はトピックにありますが、これは数学的に重く、ここではコードライトです。 – Dukeling

nをlog/n（n）に収束させるためにnが大きくなると、c2は定数です。

出典

2017-06-09 06:31:59 gue

ありがとう、それを理解しました。 –

まあ、いずれかの定数のためc1 < c < c2我々はn0ようにf(n)/g(n)ことが[c1..c2]範囲のためになります見つけることができることを意味し、有限の限界値

lim f(n)/g(n) = c > 0 
    n -> +inf

があります場合にのみ

f(n) = Θ(g(n))

すべてn > n0（n > n0の場合はc1*g(n) < f(n) < c2*g(n)と異なる）。あなたのケースでは

f(n) = n 
g(n) = log(n)

制限は、そのような有限（と私たちは、このようなc < c2その任意のc2定数を選択することはできません）c定数はありません

lim n/log(n) = lim 1/(1/n) = lim n = +inf 
    n -> +inf  n -> +inf  n -> +inf

（のはL'Hôpital's ruleを使用してみましょう）です。

出典

2017-06-09 07:08:27

すばらしい説明!!このように考えたことはありません。 –

だけで、ここに矛盾が発生し、nの任意の値の

c2 will always be less than n。したがって、c2 ≥ n/lognは決して不可能です。

出典

2017-06-09 11:31:46

答えて

関連する問題