如何找到代码的上限和下限？ [英] How to find a upper and lower bound of code?

问题描述

我有一些代码，文本为

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

For following code, find a lower and upper bound if data for function f,g is given, and we know that is best and worst case is given, condition is fulfilled in most cases.

f：O（log（n）），下界为1

f:O(log(n)), and lower bound is 1

g：O（n），下界是（logn）^ 2

g:O(n) and lower bound is (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，我是初学者，所以请告诉我我在哪里出错。谢谢

I think that first line of my code is logn, then since n>log(n) I think that second line is O(n*log(n))and the last lines is nlogn I think because if I use summarization I get logn(n+(logn)^2-1) end then the O is O(n^2(logn)^2). And for lower bound is n(logn)^3 i am beginner in this so please tell me where I make a mistake. Thank you

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

推荐答案

您的代码格式错误，因此不清楚代码流是什么。假设您的代码实际上等效于：

Your code is badly formatted so it is not really clear what the code flow is. Assuming your code is actually equivalent to:

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

您需要找到最好的和最差的情况。

You need to find the best and the worst case performance.

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

IMHO it is easier to go from inside to the outside (at least until you get more experience):

1. 最里面的调用 f（）是 O（log（n ））在最坏的情况下， O（1）在最坏的情况下。

1. The inner-most call f() is O(log(n)) in the worst case and O(1) in the best case.

由于 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）

Since f()*f() is a constant the inner loop is O(n) times the previous step (which is f()) + 2 times f() for the initial value of j + there are also O(n) condition checks and O(n) increments which together can be expressed as a single O(n). So for the worst case it is O(n*log(n) + 2*log(n) + n) which is O(n*log(n)) and for the best case it is O(n*1 + 2 + n) which is 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）））

The if itself is just time of the calculation of f() and g(). Since the condition is mostly true, we just add the cost of the inner loop. So for the worst case it is O(log(n) + n + n*log(n)) which is O(n*log(n)) and for the best case it is O(1 + log^2(n) + n) which is O(n) (O(n) dominates O(log^2(n)))

您正确注意到的外部循环始终为 O（log（n）） 次 。因此，总复杂度为主体的 O（log（n）） 次 （+不要忘记检查并递增，如果条件大多为假，则可能有所不同）。所以最坏的情况是 O（log（n）* n * log（n）+ log（n））就是 O（n * log ^ 2（n）），最好的情况是 O（log（n）* n + log（n））就是 O（n * log（n））。

The outer loop as you correctly noticed is always O(log(n)) times. So the total complexity is O(log(n)) times of the body (+ not forget about the check and increment, this might make a difference if the condition is mostly false). So the worst case is O(log(n)*n*log(n)+log(n)) which is O(n*log^2(n)) and the best case is O(log(n)*n + log(n)) which is O(n*log(n)).

希望我没有搞不清细节。但是最重​​要的是要了解何时增加乘数。并了解简化后哪个部分占主导。

Hopefully I didn't mess up with details. But the most important thing is to understand when to add an when to multiply; and to understand which part dominates the others when you simplify.

这篇关于如何找到代码的上限和下限？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！