数据结构中大O时间复杂度推论

   大O时间复杂度的推导原则有三条:

       1.你推导到的所有时间复杂度相加的常数全部去掉,然后将去掉后的值+1;

       2.只保留去掉后复杂度的最高阶,如果有最高阶存在的话;

       3.去掉与最高阶相乘的常量,如果有最高阶的话!

下面我们根据大O推导法,结合我们程序中经常遇到的情况,推导一下时间复杂度(以java代码为例):

1.public void cal(){     int i=0; //执行一次    System.out.println(i);// 执行一次    System.exit(0);   //执行一次 } 上面的代码中总执行次数为:1 + 1 + 1. (1)根据大O推导方法第一条,将所有常量去掉,然后加1,得到最后的结果1; (2)因为第一步中的1，没有最高阶，因此第二条和三条原则均不适用.因此最后结果为1.用大O表示法表示为O(1).

2.public void cal(){            int i = 0;  //执行一次           for(ini i = 0;i < n;i++){             System.out.println(i); //执行n次         }     }     上面的代码中执行次数为: 1 + N;     (1)根据大O推论第一条,去掉所有常量后再加1,还是1 + n;     (2)根据第二条,只保留最高阶,(n的一次方,也算阶),则去掉1,只剩下n;    (3)根据第三条,因为没有与N相乘的常量,因此最后结果还是n;用大O表示法即为O(n)。

3.public void cal() {    int i = 0; //执行一次    for(int i = 0;i < n;i++) {       i = i * 2; //执行次数大致是n的一半时间    } } 上面的代码中,由于受常量2的影响,因此执行次数为1 + 2 的X次方(X为执行次数),则2的x次方等于n,得到x = log2N;因此最后的执行次数为 1 +log2N; (1)根据第一条原则,去掉所有常量,后再加1,还是1 + log2N; (2)根据第二条原则,只保留最高阶,则去掉1,变为log2N; (3)根据第三条原则,去掉与最高阶相乘的常量后为logN,因此最后结果    为O(logN);

4.public void cal(){       int i = 0;j = 0; //执行一次      for(i = 0;i < n;i++) {         for(j = 0;j < n;j++) {            System.out.println(j);        }     } } 上面的代码执行次数为1 + n * n即为1 + n2; (1)根据第一条原则,结果还是1 + n2; (2)根据第二条原则,只保留最高阶，结果为 n2; (3)根据第三条原则,因为没有与最高阶相乘的常量,因此最后结果为: n2,表示为:O(n2);

5.public void cal(){       int i = 0;j = 0; //执行一次      for(i = 0;i < n;i++) {         for(j = 0;j < M;j++) {            System.out.println(j);        }     } } 上面代码的执行次数为1 + n * m; (1)根据第一条原则,还是1 + n * m; (2)根据第二条原则,去掉所有常量,保留最高阶,变为n*m; (3)根据第三条原则,去掉与最高阶相乘的常量,因为没有相乘的常量,因此最终结果还是n * m,表示为O(n*m);

6.public void cal(){       int i = 0;j = 0; //执行一次      for(i = 0;i < n;i++) {         for(j = i;j < n;j++) {            System.out.println(j);        }     } } 注意上面的代码中j初始值为i,因此推导相对复杂一些,当i =1时,执行了执行了n*(n - 1)次,当i =2时,执行了n*(n -2)次,其它以此类推,我们以执行二次为例来推导,该为n*(n -1) + n*(n - 2),则最后的结果为n*n - n + n*n -2n即为2n2-3n; (1)根据第一条原则,因为没有相加的常量,因此结果为2n2-3n; (2)第二条原则,只保留最高阶,结果为2n2; (3)第二条原则,去掉与最高阶相乘的常量,结果为n2,因此最后结果即为n2,表示为O(n2);

以上即为我们程序中常见代码的时间复杂度的推论方式.