通过一个实例学会时间复杂度的计算

时间复杂度的定义      一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。 根据定义，可以归纳出基本的计算步骤  1. 计算出基本操作的执行次数T(n)      基本操作即算法中的每条语句（以;号作为分割），语句的执行次数也叫做语句的频度。在做算法分析时，一般默认为考虑最坏的情况。 2. 计算出T(n)的数量级      忽略常量、低次幂和最高次幂的系数，     令f(n)=T(n)的数量级。 3. 用大O来表示时间复杂度      当n趋近于无穷大时，如果lim(T(n)/f(n))的值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，即为时间复杂度。

一个示例：  (1) int num1, num2; (2) for(int i=0; i     int sum = 1;     sum = count * (count+1)/2;        System.out.print(sum); } 这样算法的时间复杂度将由原来的O(n)降为O(1)，大大地提高了算法的性能。  3.混合情况（多个方法调用与循环）的复杂度分析  例如： public void suixiangMethod(int n){     printsum(n);//1.1     for(int i= 0; i        for(int k=0; k         System.out.print(i,k); //1.3       }   } suixiangMethod 方法的时间复杂度需要计算方法体的各个成员的复杂度。 也就是1.1+1.2+1.3 = O(1)+O(n)+O(n2) ----> 忽略常数 和 非主要项 == O(n2) -------------------------------------------------------------------------------------------------- 更多的例子  O(1)  交换i和j的内容 temp=i; i=j; j=temp;                     以上三条单个语句的频度为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 O(n2)      sum=0；                /* 执行次数1 */     for(i=1;i