大写符号工作

Question

我是时间复杂的新使用Big-O表示法我有三个例子，我试图找出大（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

这里是：

1. O（m / 3 * n * 5）= O（mn * C）= O（mn）
2. O（n +（n - 10）* log（m））= O（n * log（m））
3. O（（n-2）*（n-3）/ 2 + log（m））= O（n2 + log（m））= O（n2）

请下一次格式化由括号更清晰定义的代码块。 在3. O（n2 + log（m））→O（n2）中，因为f（x）= x2> 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++;
    }
}

因为在大O常数中无关紧要，即O（5）= O（1）或O（18 * x5）= O（x5）。 例如，这就是为什么big-O中的log没有基数：O（log2x）= 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（n2 + log（m））。

现在让take a look函数为x2和log（x）。如您所见，x2的增长速度远远快于log（x）。当x→+∞时，可以通过研究l（x）= log（x）/ x2的极限来实现证明。它等于零。 这就是为什么在和x2 + log（x）中，第一个术语占主导地位。所以[x2 + log（x）] / x2 = 1 + o-小（x），即它们在复杂性方面是相等的。这就是O（n2 + log（m））= O（n2）的原因。

原始方程有两个不同的变量依赖。如果它们都是独立的，最好“计算”它们：O（n2 + log（m））。