-2

要素が実行時xにソートされた配列Aにあるかどうかを判断するにはどうすればよいですか?Ω(log(n))

私の最初の答え: 二分探索を使用し、その高さが少なくとも log_3(n) であることを示す決定木を作成します。したがって、高さのある三分木にhは3^h葉があり、log_3(n) ∈ Ω(log(n)) です。

4

1 に答える 1

0

The decision tree is a good instinct. Now imagine not actually creating the tree, but performing the same search through it anyway....

于 2012-06-18T18:25:55.643 に答える