如何找到代码的上限和下限？

Question

我有一些代码，正文是

对于以下代码，如果给定函数 f,g 的数据，则找到下限和上限，并且我们知道给出了最好和最坏的情况，在大多数情况下都满足条件。

f:O(log(n))，下限为 1

g:O(n) 下限为 (logn)^2

我认为我的代码的第一行是 logn，然后因为 n>log(n) 我认为第二行是 O(n*log(n))，我认为最后一行是 nlogn，因为如果我使用总结我得到 logn(n+(logn)^2-1) 结束然后 O 是 O(n^2(logn)^2)。下限是 n(logn)^3 我是这方面的初学者，所以请告诉我哪里出错了。谢谢

for(int i=n;i>0;i/=2)
if(f()<=g())
for(int j=f()*f();j<n;j++)
f()

Answer 1

您的代码格式不正确，因此不太清楚代码流是什么。假设您的代码实际上等同于：

for(int i=n; i>0; i/=2) {
  if(f()<=g()) {
    for(int j=f()*f(); j<n; j++) {
      f();
    }
   }
}

您需要找到最佳和最差情况下的性能。

恕我直言，从内到外更容易（至少在你获得更多经验之前）：

inner-most调用f()在最坏的情况下是O(log(n))，在最好的情况下是O(1)。
因为f()*f()是一个常量，内循环是O(n)次前一步（即 f()）+ 2 次 f() 的初始值 j + 还有 O(n) 条件检查和 O(n) 增量，它们一起可以表示为单个O(n)。因此，对于最坏的情况，它是 O(n*log(n) + 2*log(n) + n)，即 O(n*log(n))，对于最好的情况，它是 O(n*1 + 2 + n)，即 O(n)
if本身就是f()和g()的计算时间。由于条件大部分为真，我们只需添加内循环的成本。因此，最坏的情况是 O(log(n) + n + n*log(n))，即 O(n*log(n))，最好的情况是 O(1 + log^2(n) + n)，即 O(n)（O(n) 支配 O(log^2(n)) )
您正确注意到的外循环始终是 O(log(n)) 次。所以总复杂度是 O(log(n)) 倍的 body （+不要忘记检查和递增，这可能如果条件大部分为假，则有所不同）。所以最坏的情况是 O(log(n)*n*log(n)+log(n)) 即 O(n*log^2(n)) 最好的情况是 O(log(n)*n + log(n)) 即 O(n*log(n)).

希望我没有搞砸细节。但最重要的是了解何时加，何时乘；并在简化时了解哪一部分支配其他部分。

如何找到代码的上限和下限？

How to find a upper and lower bound of code?

algorithm

complexity-theory