大 o 符号工作

Question

我是使用 Big-O 表示法的时间复杂度方面的新手我有三个例子我试着找出 Big(o)

第一个例子是

 sum = 0;
 for(i=0; i<m/3; i++){
 System.out.println(“*”);
 for(j=0; j<n; j++)
 for(k=0; k<10; k=k+2)
 sum++;
 }

我认为这个是 O(mn)，第一个循环工作 m/3 次，第二个循环工作 n 次，第三个循环工作 10 次然后 O(mn)

第二个例子是

sum = 100;
for(i=0; i<n; i++){
sum++; 
}
for(j=10; j<n; j++)
for(k=1; k<m; k*=2)
 sum++;

Big-O = O(log(m))，其中执行的操作数为 n + ( (n - 10) * log(m) )

第三个例子是

  sum = 0;
  for(i=2; i<n; i++){
  for(j=3; j<n; j+=2){
         sum++;
  }}
 for(k=1; k<m; k*=2)
 sum++;

这里我认为Big-O = log(m)n^2 ???

正确吗？？？

Answer 1

这里是：

O(m/3 * n * 5) = O(mn * C) = O(mn)
O(n + (n - 10) * log(m)) = O(n*log(m))
O((n-2)*(n-3)/2 + log(m)) = O(n² + log(m)) = O( n²)

下次，请将大括号定义的代码块格式化得更清晰。
在 3. O(n² + log(m)) → O(n²) 因为 f(x) = x² > g(x) = log(x), 当 x → +∞.

UPD。您的代码（格式稍微好一点）：

sum = 0;
// let's go from inner most loop: (n - 3)/2 actions or simpler n/2 or just n
for(i=2; i<n; i++) {
    for(j=3; j<n; j+=2) {
        sum++;
    }
}

因为在 big-O 中常数无关紧要，即 O(5) = O(1) 或 O(18 * x⁵) = O(x⁵).
例如，这就是为什么 big-O 中的 log 没有基数：O(log₂x) = O(log(x) / log(2)) = O(log(x) * Const) = O(log(x))，其中 log - 是自然对数（底数是 e）

我们再来一次：

sum = 0;    
// n actions in inner loop n times. So it's O(n^2)
for(i=2; i<n; i++) {
    for(j=3; j<n; j+=2) {
        sum++;
    }
}
// THEN there're another log(m) actions
for(k=1; k<m; k*=2) {
    sum++;
}

所以我们求和：O(n² + log(m)).

现在 take a look 函数 x² 和 log(x)。如您所见，x² 的增长速度比 log(x) 快得多。通过研究当x → +∞时l(x) = log(x) / x²的极限可以得到证明。它等于零。
这就是为什么在总和 x² + log(x) 中第一项占主导地位。所以 [x² + log(x)] / x² = 1 + o-small(x)，即它们在条件上相等的复杂性。这就是为什么 O(n² + log(m)) = O(n²).

原方程有两个不同的变量依赖。如果它们都是独立的，最好 "count" 它们都：O(n² + log(m)).

大 o 符号工作

Big o notation work

big-o