我目前正在学习Big Oh的基本算法。我想知道是否有人可以向我展示使用Big Oh的Java中（n log n）的代码会是什么样子，或者将我引导到任何存在的SO页面。
由于我只是一个初学者，我只能在编写代码之前想象一下代码。因此，从理论上讲（至少），它应该包含一个for循环，其中我们有n次的东西。然后对于 log n，我们可以使用 while 循环。因此，循环执行 n 次，while 循环执行日志基数 2 次。至少这是我在脑海中想象它的方式，但看到代码会把事情弄清楚。
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 循环应清晰;它是执行时间。现在进入内部循环。在内循环中，您取并始终将其除以 。所以，你问自己：我可以除以多少次？nn2n2
事实证明，这是.事实上，的基数是 ，但在 Big-O 表示法中，我们删除了基数，因为它只会增加我们不感兴趣的因素。O (log n)log2log
因此，您正在执行一个循环时间，而在该循环中，您正在执行另一个循环时间。所以，你有.nlog(n)O(n) * O(log n) = O(n log n)
一个非常流行的O（n log n）算法是合并排序。http://en.wikipedia.org/wiki/Merge_sort 例如算法和伪代码。该算法的对数 n 部分是通过将问题分解为更小的子问题来实现的，其中递归树的高度为 log n。
许多排序算法的运行时间为O（n log n）。有关更多示例，请参阅 http://en.wikipedia.org/wiki/Sorting_algorithm。
