Java 大哦 (n log n)

Big Oh for (n log n)

提问by hherklj kljkljklj

I am currently studying basic algorithms for Big Oh. I was wondering if anyone can show me what the code for (n log n) in Java using Big Oh would be like or direct me to any SO page where one exists.

我目前正在研究 Big Oh 的基本算法。我想知道是否有人可以使用 Big Oh 向我展示 Java 中 (n log n) 的代码是什么样的，或者将我引导到任何存在的 SO 页面。

Since I am just a beginner, I can only imagine the code before I write it. So, theoretically (at least), it should contain one for loop where we have something of n times. Then for the log n, we can use the while loop. So then the loop is executed n times and the while loop is executed log base 2 times. At least that is how I am imagining it in my head but seeing the code would clear things up.

由于我只是一个初学者，我只能在编写代码之前想象一下代码。因此，理论上（至少），它应该包含一个 for 循环，其中我们有 n 次。然后对于 log n，我们可以使用 while 循环。然后循环执行 n 次，while 循环执行 log base 2 次。至少这是我在脑海中想象的方式，但看到代码会清除一切。

回答by rcs

A very popular O(n log n) algorithm is merge sort. http://en.wikipedia.org/wiki/Merge_sortfor example of the algorithm and pseudocode. The log n part of the algorithm is achieved through breaking down the problem into smaller subproblems, in which the height of the recursion tree is log n.

一个非常流行的 O(n log n) 算法是归并排序。http://en.wikipedia.org/wiki/Merge_sort例如算法和伪代码。算法的 log n 部分是通过将问题分解为更小的子问题来实现的，其中递归树的高度为 log n。

A lot of sorting algortihms has the running time of O(n log n). Refer to http://en.wikipedia.org/wiki/Sorting_algorithmfor more examples.

很多排序算法的运行时间都是O(n log n)。有关更多示例，请参阅http://en.wikipedia.org/wiki/Sorting_algorithm。

回答by mabn

http://en.wikipedia.org/wiki/Heapsort

http://en.wikipedia.org/wiki/Heapsort

Simple example is just like you described - execute n times some operation that takes log(n) time. Balanced binary trees have log(n) height, so some tree algorithms will have such complexity.

简单的例子就像你描述的那样 - 执行 n 次需要 log(n) 时间的操作。平衡二叉树有 log(n) 高度，所以一些树算法会有这样的复杂度。

回答by productioncoder

int n = 100
for(int i = 0; i < n; i++) //this loop is executed n times, so O(n)
{
    for(int j = n; j > 0; j/=2) //this loop is executed O(log n) times
    {

    }
}

Explanation: The outer for loop should be clear; it is executed ntimes. Now to the inner loop. In the inner loop, you take nand always divide it by 2. So, you ask yourself: How many times can I divide nby 2?

说明：外部for循环应该是清晰的；它是执行n次数。现在到内循环。在内部循环中，您采用n并始终将其除以2。所以，你问自己：我有多少次可以把n通过2？

It turns out that this is O (log n). In fact, the base of logis 2, but in Big-O notation, we remove the base since it only adds factors to our logthat we are not interested in.

事实证明，这是O (log n). 事实上， 的基数log是2，但在大 O 符号中，我们删除了基数，因为它只会增加log我们不感兴趣的因素。

So, you are executing a loop ntimes, and within that loop, you are executing another loop log(n)times. So, you have O(n) * O(log n) = O(n log n).

因此，您正在执行一个循环n时间，并且在该循环中，您正在执行另一个循环log(n)时间。所以，你有O(n) * O(log n) = O(n log n)。

回答by Daniel Renshaw

Algorithms with a O(.)time complexity involving log n's typically involve some form of divide and conquer.

O(.)时间复杂度涉及log n的算法通常涉及某种形式的分而治之。

For example, in MergeSortthe list is halved, each part is individually merge-sorted and then the two halves are merged together. Each list is halved.

例如，在MergeSort 中，列表被减半，每个部分单独合并排序，然后将两半合并在一起。每个列表减半。

Whenever you have work being halved or reduced in size by some fixed factor, you'll usually end up with a log ncomponent of the O(.).

每当您的工作因某个固定因素而减半或缩小时，您通常最终会log n得到O(.).

In terms of code, take a look at the algorithm for MergeSort. The important feature, of typical implementations, is that it is recursive (note that TopDownSplitMergecalls itself twice in the code given on Wikipedia).

代码方面，看一下MergeSort的算法。典型实现的重要特征是它是递归的（注意TopDownSplitMerge在维基百科给出的代码中调用了两次）。

All good standard sorting algorithms have O(n log n)time complexity and it's not possible to do better in the worst case, see Comparison Sort.

所有好的标准排序算法都有O(n log n)时间复杂度，在最坏的情况下不可能做得更好，请参阅比较排序。

To see what this looks like in Java code, just search! Here's one example.

要查看 Java 代码中的内容，只需搜索! 这是一个例子。