算法时间复杂度分析
将算法中基本操作的执行次数作为算法时间复杂度的度量；
（换句话说：
算法中基本操作的重复执行的次数就是算法的计算量，将其大小作为算法的时间复杂度
注：语句的频度指的是该语句重复执行的次数。
算法的时间复杂度算的是语句总的执行次数T（n）是关于问题规模n的函数。注意是总的执行次数。不是某一句的频度。
）
算法的时间复杂度取决于问题的规模，待处理数据的初态。
常用时间复杂度：
O(1) ≤O(log2(n)) ≤O(n) ≤O(nlog2(n)) ≤O(n^2)≤ O(n^3) ≤.....≤O(n^k)≤ O(2^n)
注：越小越优
O的形式定义为：若f(n)是正数n的一个函数，则O(n)表示一个正常数M，使得当n≥n0时满足｜O(f(n))｜≤ M*|f(n)|,也就是O(f(n))给出了函数O(f(n))给出了f(n)的一个上界。
具体步骤：
(1)确定算法中的基本操作以及问题规模
1.找基本操作：多数情况下取最深循环内的语句所描述的操作作为基本操作。
2.确定规模：一般是参数n
2)确定基本操作执行情况计算出规模n的函数f(n)，并确定时间复杂度为T(n)=O(f(n)中增长最快的项/此项的系数)
1.计算出n的函数f(n)
2.找出次方最高项，去除系数，即为时间复杂度。
注：一般依照使得基本操作执行次数最多的输入来计算时间复杂度，即最坏的情况作为算法时间复杂度的度量。
常用规则：
a) 加法规则
T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O（max(f(n),g(n))）
例：已知两个长度分别为m和n的升序链表，若将他们和并为一个长度为m＋n的降序链表，则最坏情况下的时间复杂度为 O(max(m,n))
b) 乘法规则
T(n) = T1(n) x T2(n) = O(f(n)) x O(g(n)) = O（f(n)xg(n)）
例： for(i=0 ; i<n; i++)
for(j=0;j<m;j++)
a[i][j]=0;
此处使用乘法规则 时间复杂度为O(mxn)
注：递归程序一般使用公式进行递推
一般是求T（n）的通项，T(n)为时间复杂度，由递推公式求通项
非递归程序比较简单，可以直接累计次数。
常见的时间复杂度：
对于for语句时间复杂度的计算：
一层for语句：
例如：for(i=0;i<n;i++)
｛
x++; //计算该语句的频度
｝
该语句的频度为： n-0 (若式中为i<=n 则频度为n-0+1)
二层for语句：
时间复杂度为:O(n)
例如for(i=2; i<=n;i++)
for(j=2;j<=i-1;i++)
{
++x; //计算这里的频度
}
计算方法：
依次对i的值进行计算：
当i＝2时，第二个for语句执行了0次；
当i＝3时，第二个for 语句执行了1次；
.....
当i＝n时，第二个for语句执行了n-1-2+1次；
i一共取了n－2＋1次值
根据等差数列求和公式，频度为：(0＋n-2)(n-1)/2
得时间复杂度为：O(n^2)
三层for 语句：
例如for(i=1;i<=n;i++){
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x+=delta; //计算该语句的频度
}
当i＝1时，执行了1次
当i＝2时，执行了3次
当i＝3时，执行了6次
当i＝n时，执行了
总的次数为 1＋（1＋2）＋（1＋2＋3）＋.....＋（1＋2＋3＋....+N）
即频度为
对数阶
int count =1;
while (count<n)
{
count = count *2;
}
由于每次count乘以2之后，就距离n更近了一分，也就是说，有多少个2相乘后大于n，则会推出循环，有2^x=n 得到x＝log2n，所以这个循环的时间复杂度为O(logn)
类似于这种whlie的情况通常判别式中的值会在循环中改变。解决方法是：依次求得改变后的值，找出普遍的规律（即与执行次数之间的关系），然后将执行次数用n表示，即为f（n）