时间复杂度
算法时间复杂度定义
时间复杂度的定义是：如果一个问题的规模是n，解决这一问题所需算法所需要的时间是n的一个函数T(n)，则T(n)称为这一算法的时间复杂度。
算法中基本操作的执行次数。既然是T(n)的函数，随着模块n的增大，算法执行的时间的增长率和T(n)的增长率成正比，所以T(n)越小，算法的时间复杂度越低，算法的效率越高。 通过时间的复杂度来看算法执行的好坏。
常见的算法时间复杂度
时间复杂度与空间复杂度区别
时间复杂度：全称渐进式时间复杂度，表示算法的执行时间与数据规模的增长关系； 空间复杂度：全称渐进式空间复杂度，表示算法的存储空间与数据规模增长关系；
计算时间复杂度方法
- 确定算法中的基本操作以及问题的规模。
- 根据基本操作执行情况计算出规模n的函数f(n),并确定时间复杂度为T(n)=O( f(n)中增长最快的项/此项的系数 )。
通俗来讲：
- 用常数1替换所有加法常数；
- 在修改后的运行次数的函数中，只保留最高阶项；
- 如果最高阶项不是1(例如O(1)),则把该项的系数除掉，得到O；
实战分析
分析一
int i=0,n=100; /*执行了一次*/
i=n/2+n; /*执行了一次*/
printf("i=%d",i); /*执行了一次*/非常容易分析出这段代码一共执行了3次，那么时间复杂度就是O(3)吗，这样想是错误的，回头看之前计算时间复杂度方法，它是f(n)=3,所以应该把3改为1，即O(1)。再来一段代码：
int i=0,n=100; /*执行了一次*/
i=n/2+n; /*执行了一次*/
printf("i=%d",i); /*执行了一次*/
printf("i=%d",i); /*执行了一次*/
printf("i=%d",i); /*执行了一次*/
printf("i=%d",i); /*执行了一次*/
printf("i=%d",i); /*执行了一次*/这段代码一共执行了7次，那么时间复杂度为多少呢，还按照上面所说的，它是f(n)=7,把7改为1，即O(1)。比如像这种代码是具有恒定的执行时间的，也就是代码不会因为问题规模n的变化而发生变化，这里都记为O(1).
分析二
void fun(int n)
{
int i=1,j=100;
while(i<n)
{
++j;
i+=2;
}
}显然n确定以后，循环的开始结束都是与i有关的，且每次自增2，假设m次后结束循环，那么i应该等于1+2m，那么就有n=1+2m，因为要是执行次数，也就是解得m=(n-1)/2，此时可以看出n/2增长的是最快的项需要把前面的系数除掉即可得到O，即(n/2)/(1/2)=n，得O(n). 接下来个复杂点的：
int i=1;
while(i<n)
{
i=i*2;
}推导时间复杂度，最重要的就是要分析算法的执行次数。这里i起始值为1，每次都乘2，也就意味着每次都会距离n近一些，那么何时超过n而终止循环呢，是i22222...*2>n,那么假设k次之后大于n，就有2^k=n,得出k=logn。 再来一段代码：
int i,j,x=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
x++;
}外循环执行n次，内循环也是执行n，则O(n^2). 最后来一段代码：
int i,j,x=0;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
x++;
}由于当i=0，时内循环执行了n次，i=1时，执行了n-1次，...i=n-1时，执行了1次，那么总次数为 n+(n-1)+(n-2)+..+1=n(n+1)/2,那么就是n^2/2,即O(n^2).
其他时间复杂度
- 最好情况时间复杂度：指的是在最理想状态下，执行这段代码所需的时间；
- 最坏情况时间复杂度：指的是在最糟糕情况下，执行这段代码所需的时间； 要查找的变量 x 可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)即最好时间复杂度。但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)即最坏时间复杂度。所以，不同的情况下，这段代码的时间复杂度是不一样的。
- 平均时间复杂度：全称叫加权平均时间复杂度或者期望时间复杂度。
- 均摊时间复杂度：对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。均摊时间复杂度就是一种特殊的平均时间复杂度