大哦为（n log n） [英] Big Oh for (n log n)

问题描述

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

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.

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

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.

推荐答案

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 多少次？

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

事实证明这是 O（日志n）。实际上， log 的基数是 2 ，但是在Big-O表示法中，我们删除了基数，因为在我们不感兴趣的 log 中添加了一些因素。

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

因此，您正在执行循环 n 次，并且在该循环中，您正在执行另一个循环 log（n）次。因此，您有 O（n）* O（log n）= O（n log n）。

So, you are executing a loop n times, 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）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！