問題タブ [big-theta]

私はアルゴリズムを設計し、シータを結論付けるために上限と下限を見つけようとしています:

ご覧のとおり、kruskal アルゴリズムに非常に似ています。ここで私の問題は、find-setの実行時間を理解できないことです

私が持っている他の部分について：

makeset O(v) sorting O(ElogE) union O(1) しかし、find set の計算方法がわかりませんか? (また、union の計算された実行時間が true かどうか教えてください)

Kruskal アルゴリズムの実行時間を分析したところ、O(ElogE+Elogv+v) が得られました。

私は教授に尋ねたところ、グラフが非常にまばらで、多くの孤立した頂点がある場合、V が E を支配し、そうでない場合は E が V を支配し、その理由が理解できないと彼は言いました。グラフがまばらではないが、それでも V が E より大きい例を挙げることができます

この混乱を解消するのを手伝ってくれる人はいますか?

2n+5 が O(n²) であることを示せという宿題があります。

これは私が試して解決するためにしたことです：

k = 1 を選択し、n > 1 と仮定したため、f(n)/g(n) = (2n+5)/n² < (2n+5n)/n² = 7n/n² = 7/n

したがって、C は 7/n に等しい したがって、2n+5 <= (7/n)(n²) なので、2n+5 <= 7n となり、すべての n > 1 について真になります。これが、2n+5 が O( である理由です。 n²)。

それが正しいかどうかはわかりませんでした。100% 確信があるわけではありませんが、誰かがそれを確認できれば、それは素晴らしいことです。

また、シータ表記に簡略化するよう求められた別の問題についても混乱しました。

(x ^4.2 )/(1+x²)。無限大に評価したばかりなので、それはただの Θ(x ^{2.2 ) ですか?}

また、x³⋅lg(x) どこから始めればいいのかわかりません。

前もって感謝します！

これらすべてについて、実行時間を調べなければなりません。

1.

2.

3.

4.

5.

6.

7。

8.

最初のものは O(n) で、4 番目のものは O(n^2) です。これらは正しいですか？そして、他の人はどうすればいいですか？私は2番目のものと本当に混乱しています。

答えはビッグオーまたはビッグシータで表すことができます。

このアルゴリズムの実行時間を計算するにはどうすればよいでしょうか。将来同様の問題を解決できるようになりますか?

入力サイズ n は再帰関係を満たします (n>= 1 の場合)

T を、左側のサブツリーが T _Lで、右側のサブツリーが T _Rである AVL ツリーとします。_{|T L} |としましょう。および |T _R | それぞれ、左と右のサブツリーのノード数になります。

|T R | |T _R | ≠ Θ(|T _R |) とその逆ですが、方法がわかりません。1 つのツリーが完全な AVL ツリーで、もう 1 つのツリーが最小の AVL ツリー (フィボナッチ ツリー) である場合と関係があると思いますが、そこから何をすべきかわかりません。

f(n) ∈ Ѳ(g(n)); 2^(f(n)) ∈ Ѳ(2^(g(n))) であることをどのように証明できますか? 大きなシータの制限を使用して、第一原理を使用しようとしましたが、うまくいきませんでした。助けてください