算法的时间复杂度

常见的算法时间复杂度由小到大依次为:

常数阶 O(1) < 对数阶 O(log2n) < 线性阶 O(n) < 线性对数阶 O(nlog2n) < 平方阶 O(n^2) < 立方阶 O(n^3) < k次方阶 O(n^k) < 指数阶 O(2^n)

算法的时间复杂度取决于：问题的规模和待处理数据的初态。

计算下列各算法的时间复杂度

1. x=90;y=100;

   while(y>0)

        if(x>100)

             {x=x-10;y--;}

        else  x++;

2. for(i=0; i<n; i++)

        for(j=0; j<m; j++)

             a[i] [j] =0;

3. s=0;

   for(i=0; i<n; j++)

        for(j=0; j<n; j++)

            s+=B[i] [j];

   sum=s;

4. i=1;

   while(i<=n)

        i=i*3;

5. x=0;

   for(i=1; i<n; i++)

       for(j=1; j<=n-i; j++)

           x++;

6. x=n; //n>1

   y=0;

   while(x>=(y+1)*(y+1))

          y++;

   答：

   第一:   O(1)    理由：算法执行的再大，算法的时间复杂度都是1。

   第二：O(n*m)   理由：for循环两次，一次n，一次m，所以是n*m。

   第三：O(n^2)   理由：for循环两次，两次都说n，所以n的2次方。

   第四：O(log2n)   理由：n等于1，2，3时循环1次，n等于4，5，6 ....12时循环2次，以此类推得出 log2n。

   第五：O(n^2)  理由：两次for循环，循环n次，所以n的2次方。

   第六：O(√n)   理由：x大于等于(y+1)的平方，所以循环更号n次。