問題タブ [little-o]

Big-O表記O(n)とLittle-O表記の違いは何o(n)ですか?

私は大規模なデータ セットを使用するアルゴリズムのコースでこの課題を抱えてここに座っています。Big-Oh には完全に自信がありますが、Little-Oh 表記法を使用すると混乱してしまいます。

私は課題の解決策を望んでいないので、提示しません。代わりに、私の質問は、時間の複雑さo(log n)をどのように解釈するかです。

定義から、アルゴリズム A は o(log n) よりも漸近的に遅く成長しなければならないことはわかっていますが、これがアルゴリズムが一定時間で実行されなければならないことを意味するのか、それとも log n であってもよいのかはわかりませんc = 1 のような特定の条件下、または実際にlog (n-1)である場合。

アルゴリズムの実行時間がO(log n)であるとしますが、実際には 2 回の反復を行い、そのため c = 2 ですが、2*log nは依然としてO(log n)です。これが成り立たないと言うのは正しいですか?リトルオー？

どんな助けでも大歓迎です。明確にするために厳密に必要な場合は、課題を提供します

私がここでlittle-oを求めていることに注意してください（ここで同様の質問を参照してください）-大きなOhの場合は明らかに間違っています-little-oの場合は正しいと感じますが、それを証明できないようです...

編集：私が議論を提起したことをうれしく思います:)簡単にするためにf、g>0と仮定します

私は、任意の定数 , (N の小さな O) に対してそれを証明しようとしていkますlog^k N = o(N)。

小さな o について私が知っているのは、よりも遅い速度T(n) = o(p(n))で成長する形に従うということだけです。また、何が何なのか分からないので、制限して使用することは本当にできません。誰かが私を始めるのを手伝ってくれませんか!T(n)p(n)L'hopital rulef(n)g(n)

big-Oとlittle-o表記の原理的な違いは理解できたと思います。big-Oしかし、実際になぜもっと人気があるのか​​誰か教えてもらえますか?

宿題として、5 ^{nが 7 n}の little-o、Θ、または little-ω のいずれであるかを、数学的な正当性を考慮して決定する必要があります。次に、両辺の対数を取った後、これを繰り返す必要があります。

何を求められているのか理解に苦しむ。私が持っている最良の推測は、A(n) = 5 ⁿおよび B(n) = 7 ⁿと言ってから、l'Hopital の規則を使用することですが、どのように進めればよいかわかりません。私は正しい方向へのキックを探しているだけです。

ありがとう！

プライオリティ キューに と の 2 つの操作があるinsert場合broken_min。Wherebroken_minは、最初または 2 番目の最小項目のいずれかを返します。

これらの両方を o(logn) 時間で実装することはできません。これは、挿入がbroken_minを使用し、最大値があるかどうかを確認するためにさらにチェックを行う必要があるためだと思います.

これは正しい推論ですか？

この1つの問題で困っています

基本的に私は降りることができます

しかし、どうすれば残りを解決できますか？