隣接リストとバイナリサーチの平均時間複雑度（別個の2つの質問）

Question

ソートされた配列とバイナリ検索ツリーで成功したバイナリ検索の平均時間複雑度は、O（log（n））？また

、最悪の場合の時間の複雑さは、どちらも同じO（N）ですか？

---

グラフの隣接リストを描画するときは、この問題の順序はありますか？ （2及び3の切り替え方法を最初の行に通知）これに

：例えば、これを変更することが間違っているであろう

Answer 1

最悪平均ソートされた配列を検索するための引数はO（Log n）です。配列がソートされていれば、要素が存在しないと結論づけるために、ほとんどのO（Log n）ジャンプを行います。

BSTでは、ツリーが完全に歪んでリンクリストのように動作している最悪の場合に、最悪と平均がそれぞれO（n）とO（Log n）になります。

---

彼らのためには、（DFSが別のノードに別のパスを返すように）あなたが行うことができるいくつかの実行には問題かもしれませんが、両方の隣接リスト表現は完全に有効です。