这个算法的复杂性是多少？

Question

我需要计算这段代码的复杂性.我知道它是O(n),但我需要公式中的证据.例如,循环具有复杂性1 + 3*n + n*f(body).

代码1:

int i = 0;
int t = 0;
int j = n/2;
while (i<n) {
    while (t<n/2) {
        t++;
        i++;
    }
    while (j<n) {
        j++;
        i++;
   }

}

UPD:我也需要计算这段代码的复杂性.它与Code 1不同吗？

代码2:

int k = 0;
int i = 0;
int t = 0;
int j = n/2;
while (i<n) {
    k=0;
    while ((t<n/2) && (k<=10)) {
         t++;
         i++;
         k++;
    }
    k=0;
    while ((j<n) && (k<=10)) {
         j++;
         i++;
         k++;
    }
}

Answer 1

在t的while循环中,i应该从0递增到(n/2)-1并且在下一个j的while循环中递增到i

因此,在一次迭代中,我期望执行外循环!

此外,t和j的while循环执行彼此互斥.但是,它们通常将i --- t从o增加到n/2 - 1,j从n/2增加到n-1.

因此,代码复杂性

= i-loop*的单次迭代(内部循环的复杂性)

= O(1)*(基于t的循环的复杂性基于j的循环的UNION复杂性)

= O(1)*(O(n/2)UNION O(n/2))

= O(1)*O(n/2)

= O(n).

所以,你的结论是正确的.这段代码的复杂性是O(n)......

在谈论代码2时,它与代码1没有太大区别!只添加了一个新的变量k,它将导致内循环只重复10次,因为它与&&条件有界限.

此外,基于i的循环将迭代n/20次,如在i-loop的1次迭代中,i在执行两个内循环后被修改为20 ...因此,我将完成其对较小的测试比n,在n/20次迭代之后.因此,基于i的循环的算法性能= O(n/20)......

因此,代码2的复杂性

= i-loop*的多次迭代(内部循环的复杂性)

= O(n/20)*(O(1)UNION O(1))
//内循环将运行10次迭代,因此,它们的复杂性为O(1).

= O(n).

因此,代码2的复杂性将是O(n)......