o（logn）は常に木ですか？

StackOverflow https://stackoverflow.com/questions/2308779

質問

（バイナリ検索）ツリーの操作には、ツリーの高さがlognであるため、o（logn）最悪のケースの実行時間が常に表示されます。アルゴリズムがlognの関数として実行時間を持っていると言われているのだろうか、例：m + nlogn、それは（増強された）ツリーを含む必要があると結論付けることができますか？

編集：あなたのコメントのおかげで、私は今、Divide-ConquerとBinary Treeが視覚的/概念的に非常に似ていることに気付きました。私は2つの間でつながりを作ったことがありませんでした。しかし、私は、O（logn）がBST/AVL/赤黒樹の特性を持たない木を含む分割征服アルゴではない場合を考えています。

これは、実行時間がO（n + mlogn）であるFind/Union操作を備えた分離セットデータ構造であり、nは要素の＃であり、MはFind操作の数です。

STHが足りない場合はお知らせください。しかし、ここでDivide-Croulがどのように機能するかはわかりません。この（Disjoint Set）ケースでは、BSTプロパティのないツリーがあり、実行時間がlognの関数であることがわかります。ですから、私の質問は、なぜ/なぜこのケースから一般化を行うことができないのかということです。

役に立ちましたか？

解決

あなたが持っているものは正確に後方にあります。 O(lg N) 一般に、ある種の分裂と征服アルゴリズムを意味し、分割と征服を実装する一般的な方法の1つはバイナリツリーです。バイナリツリーはすべての分割整理アルゴリズムのかなりのサブセットですが、とにかくサブセットです。

場合によっては、他の分割を変換してアルゴリズムをバイナリツリーにかなり直接征服することができます（例：別の答えのコメントは、バイナリ検索が類似していると主張する試みをすでに試みています）。ただし、別の明白な例として、マルチウェイツリー（たとえば、Bツリー、B+ツリー、またはB*ツリー）がありますが、明らかにツリーは明確には明確です いいえ バイナリツリー。

繰り返しますが、十分にひどくなりたい場合は、マルチウェイツリーをバイナリツリーのゆがんだバージョンのようなものとして表すことができるという点を伸ばすことができます。あなたが望むなら、あなたはおそらくすべての例外を、それらのすべてが（少なくとも）バイナリツリーであると言う点まで伸ばすことができます。少なくとも私にとっては、「バイナリツリー」を「分割と征服」と同義にすることだけです。言い換えれば、あなたが達成したのは、語彙をゆがめ、本質的に明確で有用な用語を抹消することだけです。

他のヒント

いいえ、ソートされた配列をバイナリ検索することもできます（たとえば）。しかし、私の言葉を受け取らないでください http://en.wikipedia.org/wiki/binary_search_algorithm

カウンターの例として：

given array 'a' with length 'n'
y = 0
for x = 0 to log(length(a))
    y = y + 1
return y

実行時間はo（log（n））ですが、ここにはツリーはありません！

答えはノーです。ソートされた配列のバイナリ検索はです O(log(n)).

対数時間を取るアルゴリズムはです 一般的に バイナリツリーの操作で見つかりました。

o（logn）の例：

  • バイナリ検索またはバランスの取れた検索ツリーを備えたソート付き配列内のアイテムを見つける。

  • 二等分によりソートされた入力配列の値を検索します。

o（log（n））は上限のみであるため、すべてのo（1）アルゴリズムのようなアルゴリズムも function (a, b) return a+b; 状態を満たします。

しかし、私はすべてのシータ（log（n））アルゴリズムに同意する必要があります。

簡潔な答え：

アルゴリズムがその分析の一部としてログ（n）を持っているからといって、ツリーが関与していることを意味しません。たとえば、以下は非常に単純なアルゴリズムです。 O(log(n)

for(int i = 1; i < n; i = i * 2)
  print "hello";

ご覧のとおり、木は関係していませんでした。ジョンは、ソートされた配列でバイナリ検索をどのように実行するかについての良い例も提供しています。これらは両方ともo（log（n））時間がかかり、作成または参照できる他のコード例があります。したがって、漸近時間の複雑さに基づいて仮定をしないでください。確かに知っておくべきコードを見てください。

木の詳細：

アルゴリズムに「木」が含まれるからといって O(logn) また。ツリータイプと操作がツリーにどのように影響するかを知る必要があります。

いくつかの例：

  • 例1）

次の不均衡なツリーを挿入または検索することになります O(n).

enter image description here

  • 例2）

次のバランスのとれた木を挿入または検索する O(log(n)).

バランスの取れたバイナリツリー：

enter image description here

バランスの取れた程度の木3：

enter image description here

追加コメント

あなたが使用している木があなたの操作がなる可能性が高いよりも「バランス」する方法がない場合 O(n) 時間ではありません O(logn). 。自己バランスをとっている木を使用する場合、挿入位相中に通常木のバランスが起こると、通常は時間がかかります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top