大哦(n log n)

Question

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

由于我只是一个初学者,我只能在编写之前想象代码.所以,理论上(至少),它应该包含一个for循环,其中我们有n次.然后对于log n,我们可以使用while循环.那么循环执行n次,while循环执行log base 2次.至少这就是我想象它的方式,但看到代码会清除.

Answer 1

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
    {

    }
}

说明:外部for循环应该清晰; 它是执行n时间.现在到了内循环.在内循环中,你采取n并始终除以它2.所以,你问自己:我有多少次可以把n通过2？

事实证明这是O (log n).事实上,基础log是2,但在Big-O表示法中,我们删除了基数,因为它只会增加log我们不感兴趣的因素.

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

Answer 2

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

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