0

I am having a hard time understanding the efficiency of an algorithm and how do you really determine that, that particular sentence or part is lg n, O (N) or log base 2 (n)?

I have two examples over here.

doIt() can be expressed as O(n)=n^2.

First example.

i=1
loop (i<n)
doIt(…)
i=i × 2 
end loop

The cost of the above is as follows:

i=1                                ... 1
loop (i<n)                         ... lg n
doIt(…)                            ... n^2 lg n
i=i × 2                            ... lg n
end loop

Second example:

static int myMethod(int n){
    int i = 1;
    for(int i = 1; i <= n; i = i * 2)
          doIt();
    return 1;
}

The cost of the above is as follows:

static int myMethod(int n){                      ... 1
    int i = 1;                                   ... 1
    for(int i = 1; i <= n; i = i * 2)            ... log base 2 (n)
          doIt();                                ... log base 2 (n) * n^2
    return 1;                                    ... 1
}

All this have left me wondering, how do you really find out what cost is what? I've been asking around, trying to understand but there is really no one who can really explain this to me. I really wanna understand how do I really determine the cost badly. Anyone can help me on this?

4

2 回答 2

5

大 O 表示法不是衡量程序将运行多长时间。它表示随着问题规模的扩大，运行时间将增加多快。

例如，如果计算某事是 O(1)，那可能是很长的时间，但它与问题的大小无关。

于 2013-09-10T14:24:15.790 回答
2

通常，您不会期望估计诸如循环迭代器之类的成本（假设存储一个整数值并更改它N的次数太小而无法包含在结果估计中）。

真正重要的是 - 就 Big-O、Big-Theta 等而言，您应该找到函数依赖性，即找到一个参数 (N) 的函数，其中：

  • Big-O：整个算法的操作计数增长小于 F(N)
  • Big-Theta：整个算法的操作计数增长等于 F(N)
  • Big-Omega：整个算法的操作计数增长大于 F(N)

所以，请记住 - 您不是试图找到许多操作，而是试图找到函数估计，即传入数据量与来自 的某个函数之间的函数依赖性，这表明操作计数的增长速度。NN

因此，例如，O(1) 表示整个算法将不依赖于N（它是恒定的）。你可以在这里阅读更多。

此外，还有不同类型的估计。例如，您可以估计内存或执行时间 - 在常见情况下这将是不同的估计。

于 2013-09-10T14:28:18.083 回答