log（n）来自O（N）表示法(Where does log(n) come from in the O(N) notation)

log（n）来自O（N）表示法(Where does log(n) come from in the O(N) notation)

我知道O（n）符号是什么，我也明白我如何得到符号O（n），O（n 2 ），......

O（n）表示我必须通过一次序列 O（n 2 ）表示我有两个嵌套循环遍历序列

但我如何获得日志（N）？

PS：我知道Collections API和一些有O（n log n）遍历时间的类。 我需要一个简单的解释。

I know what is O(n) notation and I also understand how I can get notations like O(n), O(n2), ....

O(n) means I have to get through sequence once O(n2) means that I have two nested cycles traversing sequence

But how do I get log(N)?

P.S.: I know the Collections API and some classes that have O(n log n) traversal time. I need a simple explanation.

最满意答案

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 ）复杂度。）

lg N comes about in divide-and-conquer algorithms, where you iteratively or recursively skip half of the data in a collection of N items. Binary search is the quintessential example. The insert, lookup and delete operations on binary search trees are also O(lg N).

Iteratively discarding half the elements is, in an intuitive sense, the inverse of iteratively doubling the number of elements. Doubling would produce O(2^N) elements in N iterations. Note that the binary logarithm of N is the inverse of raising two to the power N.

Sorting an array can be done in O(N lg N) by algorithms such as mergesort, but also conceptually simpler: iterate over the array and put the elements in a binary search tree. Each insert takes O(lg N) and there are N of them, so the algorithm runs in O(N lg N).

(The sort-by-BST even has worst-case O(N lg N) complexity if the tree is balanced.)