java - fnB 中 Big O 表示法的执行时间是多少？

Question

我有 2 个函数，我需要在 Big O 中找到这两个函数的执行时间，但是我对 fnB 感到困惑

int fnA(int n){
  int sum = 0;
  for(int i=0; i<n; i++){
    for(int j=n; i<j; j=j-2){
      sum += i*j;

 }
   return sum;
}

我得到了 fnA 的 O(n^2)

int fnB(int n) {
  int sum =0;
  for(int size = 1; size<n; size=2*size){
    sum+=fnA(size);
  }
   return sum;
}

由于在 fnB 的 for 循环中，大小呈指数增长。我倾向于 fnB 有一个 O(n^3)。我说的对吗，如果不对请指正，谢谢

标签： javabig-o

Answer 1

fnA运行时间为 O(n ² )。

但是，fnB它的运行时间为 O(n ² logn)，因为它有 log ₂ n 次迭代，并且每次迭代需要 O(n ² ) 时间（实际上需要 O(size ² )，但是由于size< n，我们可以对其进行限制与 O(n ² ))。

更详细的解释：

fnA(n)n在外循环中有迭代，在内循环中最多有迭代n/2，这给出了 O(n ² ) 的上限。由于fnB(n)调用的每次迭代fnA(size)，它需要 O(size ² ) == O(n ² ) （因为size< n）。

现在，循环fnB(n)将以下值分配给size：2 ^0、2 1、2 ²、...、2 ^{k ，}其中 2 ^k <= n。因此迭代次数为 k <= log ₂ n，其上限fnB为 O(n ² log ₂ n)。