19

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

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

4

4 回答 4

57 
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).

于 2013-09-26T06:52:17.050 回答
5

一个非常流行的 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。

于 2013-09-26T06:48:42.277 回答
4

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

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

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

在代码方面，看一下 MergeSort 的算法。典型实现的重要特征是它是递归的（请注意，TopDownSplitMerge在 Wikipedia 上给出的代码中调用自身两次）。

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

要查看它在 Java 代码中的样子，只需搜索！这是一个例子。

于 2013-09-26T06:53:49.937 回答
2

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

简单的例子就像你描述的那样 - 执行 n 次一些需要 log(n) 时间的操作。平衡二叉树具有 log(n) 高度，因此某些树算法将具有如此复杂性。

于 2013-09-26T06:49:35.420 回答