-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 回答