哪一个更大。O(N^2 * log(N^2)) 还是O(N^3)?

Question

我想知道下面的时间复杂度。

int i, j, k; 
for(i = 1; i <= N^2+N^2; i = i + 3)  ***//O(N^2)*** 
{
     for(j = i; j <= N ; j = j + 3)  ***//O(N^3)***
    
     { 
     } 
     
     for(k = 1; k<= N^2 ; k = k * 2)  ***//O(log(N^2)*N^2)***
      
     { 
     } 
} 

我已经解决了以下问题，但我很困惑到底是O(N^2 * log(N^2))大还是O(N^3)大？

Answer 1

这是一段非常狡猾的代码，它的运行时间比我预期的要细微得多。这就是你所拥有的。

int i, j, k; 
for(i = 1; i <= N^2+N^2; i = i + 3)
{
     for(j = i; j <= N ; j = j + 3)
     { 
     } 

     for(k = 1; k<= N^2 ; k = k * 2)
     { 
     } 
} 

@Paul Hankin提出了一个重要的观点，那就是，一旦 i 变得足够大，那第一个循环永远不会执行。因此，为了分析这个循环，我们需要考虑两种情况：一种是顶层循环执行了一定次数的迭代，另一种是没有执行。

要做到这一点，请注意，你的代码基本上等同于下面的代码，在这里，我已经将外层循环拆分成了两个更小的循环。

int i, j, k; 
for(i = 1; i <= N; i = i + 3)
{
     for(j = i; j <= N ; j = j + 3)
     { 
     } 

     for(k = 1; k<= N^2 ; k = k * 2)
     { 
     } 
} 

for(i = N+1; i <= N^2+N^2; i = i + 3)
{
     for(k = 1; k<= N^2 ; k = k * 2)
     { 
     } 
} 

解决了这个问题之后，我们来看看这些循环的独立运行情况。像往常一样，我们将使用 maxim

当有疑问时，从内到外的工作!

并开始用表示它们做了多少工作的语句替换更深的循环。让我们从从1开始数到N的循环开始吧² 通过重复加倍。该循环将运行大约对数N² = 2 log N = Θ(log n)次，所以我们得到这样的结果。

int i, j, k; 
for(i = 1; i <= N; i = i + 3)
{
     for(j = i; j <= N ; j = j + 3)
     { 
     } 

     do Θ(log N) work;
} 

for(i = N+1; i <= N^2+N^2; i = i + 3)
{
     do Θ(log N) work;
} 

同样，从i到N的循环也是Θ(N - i)的工作，所以我们得到这个。

int i, j, k; 
for(i = 1; i <= N; i = i + 3)
{
     do Θ(N - i) work;
     do Θ(log N) work;
} 

for(i = N+1; i <= N^2+N^2; i = i + 3)
{
     do Θ(log N) work;
} 

现在，关注一下这两个循环中的第二个循环。第二个循环运行Θ(N²)倍（因为（2N² - N）3=Θ（N²))，每次做O(log N)工作，所以它做Θ(N² log N）的总工作量。

int i, j, k; 
for(i = 1; i <= N; i = i + 3)
{
     do Θ(N - i) work;
     do Θ(log N) work;
} 

do Θ(N^2 log N) work;

现在我们有了第一个循环， 我们需要对i = 1，4，7，10，13等的（N - i + log N）进行求和。从i = 1，4，7，10，...，N的N - i的总和为Θ(N²)，有一种方法可以看出来，就是用这张图看出来，这个最后大致是一个三角形的面积(二次方增长的东西)。

 *
 ****
 *******
 **********
 *************

对数N运行Θ(N)次的总和就是Θ(N对数N)的总工作，所以我们最终这个循环需要Θ(N)²)时间，因为N² 主导N对数N，因此，我们有

do Θ(N^2) work;
do Θ(N^2 log N) work;

所以总体运行时间为 Θ(N² log N).

不过，回到你问的问题：Θ(N)怎么?³)与Θ(N² log N）？) 如果我们取消N² 我们知道，对数N的增长要比N缓慢得多，所以N² log N = o(N)³).

希望对大家有所帮助!

Answer 2

试着把这两个表达式做一个极限。

L = lim_{N \to \infty} N^3/(N^2 log(N^2)) = lim_{N \to \infty} N/log(N^2)

你可以在注释中找到提示。log(N^2) = 2 log(N). 现在我们有了。

L = 1/2 lim_{N \to \infty} N/log(N)

由于增长 N 不止 log(N)，我们可以得出这样的结论 L = \infty. 因此，给定的算法是 O(N^3).