创建具有给定时间复杂度的算法

Question

如何解决这类问题？我知道基本时间复杂度为 O(n)、O(n^2) 等，但是如何创建一个算法 O(m^2*(log(n))^2) 和 O(log(n^2/m))?

是否正确例如： O(m^2*(log(n))^2)

for(i=0; i<m; i++)
  for(j=0; j<m; j++)
     for(k=0; k<n; k*=2)
        for(l=0; l<n; l*=2)
            something()

第二个呢？

已编辑：因为第二个就是这样

O(log(n^2/m))=O(log(n)+log(n/m))

for(i=n;i>0;i/=2);
for(j=n/m;j>0;j/=2);

Answer 1

第四个嵌套循环是O(log n)，第三个嵌套循环是 O(log n)，第二个嵌套循环是 O(m)，第一个循环是 O(m)

因为所有这些循环都是嵌套的，所以很容易理解您必须乘以得到整体复杂度，所以它是： O(mmlog n *log n)=O(m^2 * (log n)^2).

请注意，第三个和第四个循环是 O(log n) 的原因是，例如在第四个循环中，l 在下一个循环中变为 l^2，因此如果 m 是循环重复的总数，则: l^m >=n -> m 是 O(log n) .

出于同样的原因，第三个嵌套循环也是 O(log n)。

也出于同样的原因，如果你有：

for(i=1;i<n*n/m ;i*=2)

上面的循环是 O(log (nn/m)) 因为如果你 m 是循环重复的总数那么： i^m>=nn/m -> O(log(n*n/m)).

更新

O(log(n*n/m)) = O(log n^2/m) = O(2log(n/m)) = O( log(n/m ) ) 而不是 O(log(n)+log(n/m)).

此外，如果您有：

for(i=n;i>0;i/=2)
   for(j=n/m;j>0;j/=2)
      something();

这是外循环的 O(log(n)) 和内循环的 O(log n/m) 所以整体是 O(log(n)*log(n/m )) 而不是 O(log(n)+log(n/m)).

Create algorithm with given time complexity