use*_*444 4 algorithm big-o programming-languages
我知道什么是O(n)符号,我也理解如何得到O(n),O(n 2)等符号....
但是我如何得到log(N)？
PS:我知道Collections API和一些具有O(n log n)遍历时间的类.我需要一个简单的解释.
Fre*_*Foo 12
lg N出现在分而治之的算法中,你可以迭代地或递归地跳过N个项目集合中的一半数据.二进制搜索是典型的例子.二叉搜索树上的插入,查找和删除操作也是O(lg N).
从直观的意义上说,迭代地丢弃一半元素是迭代地将元素数量加倍的倒数.加倍将在N次迭代中产生O(2 ^ N)个元素.注意,N的二进制对数是将2提高到幂N的倒数.
对数组进行排序可以通过诸如mergesort之类的算法在O(N lg N)中完成,但在概念上也更简单:迭代数组并将元素放在二叉搜索树中.每个插入都需要O(lg N)并且有N个,因此算法以O(N lg N)运行.
(如果树是平衡的,那么按BST排序甚至具有最坏情况的O(N lg N)复杂度.)