上篇算法（1）
一、函数的渐近增长
- 函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N, 使得对于所有的 n > N， f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)。
有两个算法 A 和 B ，假设两个算法的输入规模都是 n，算法 A 要做 2n+3 次操作，算法 B 要做 3n+1 次操作。觉得谁快？看下图：
算法的渐近增长.png
当 n = 1 时，算法 A 效率不如算法 B（次数比算法 B 要多一次）。而当 n = 2 时，两者效率相同；当 n > 2时，算法 A 就开始优于算法 B 了，随着 n 的增加， 算法 A 比算法 B 越来越好了，得出结论，算法 A 好过 算法 B
- 判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。
二、算法时间复杂度
1、算法时间复杂度定义
- 进行算法分析时，语句总的执行次数 T(n)是关于问题规模n的函数，进而分析 T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n)。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
用大写O()来体现算法时间复杂度的记法，称之为大O记法。
一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。
三个求和算法的时间复杂度分别是O(n)，O(1)，O(n²)。我们分别給它们去了非官方的名称，O(1)叫常数项、O(n)叫线性阶、O(n²)叫平方阶
2、推导大O阶方法
- 推导大O阶：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是大O阶
3、常数阶
高斯算法，时间复杂度不是O(3)，而是O(1)。
//第二种算法
int sum = 0, n = 100; /*执行1次*/
sum = (1 + n) * n/2; /*执行1次*/
printf("%d", sum); /*执行1次*/
这个算法的运行次数函数是f(n)=3.根据我们推导大O阶的方法，第一步就是把常数项3改为1。在保留最高阶项时发现，它根本么有最高阶项，所以这个算法的时间复杂度为O(1)。
另外，我们试想一下，如果这个算法当中的语句 sum=(1+n)*n/2有8句，即：
int sum = 0, n = 100; /*执行1次*/
sum = (1 + n) * n/2; /*执行2次*/
sum = (1 + n) * n/2; /*执行3次*/
sum = (1 + n) * n/2; /*执行4次*/
sum = (1 + n) * n/2; /*执行5次*/
sum = (1 + n) * n/2; /*执行6次*/
sum = (1 + n) * n/2; /*执行7次*/
sum = (1 + n) * n/2; /*执行8次*/
printf("%d", sum); /*执行1次*/
事实上无论n为多少，上面的两段代码就是3和10次执行的差异。这种与问题的大小无关（n的多少）,执行时间恒定的算法，我们称之具有O(1)的时间复杂度，又叫常数阶。
注意：不管这个常数是多少，我们都记作O(1)，而不能是O(3)、O(10)等其他任何数字，这是初学者常常犯的错误。
对于分支结构而言，无论是真，还是假，执行的次数都是恒定的，不会随着n的变大而发生变化，所以单纯的分支结构（不包含在循环结构中），其时间复杂度也是O(1)。
4、线性阶
- 分析算法的复杂度，关键就是要分析循环结构的运行情况。
// 线性阶
int i;
for (i = 0; i < n; i++) {
/* 时间复杂度为O(1)的程序步骤序列 */
}
```
5、对数阶
>下面的这段代码，时间复杂度又是多少呢？
int count = 1;
while (count < n) {
count = count * 2;
/* 时间复杂度为O(1)的程序步骤序列 */
}
由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n,则会退出循环。由2× = n ，得到 x = ㏒2n (2缩小)。所以这个循环的时间复杂度为O(㏒n)。
6、平方阶
下面例子是一个循环嵌套，它的内循环刚才我们已经分析过，时间复杂度为O(n)。
int i, j;
for(i = 0, i < n; i++)
{
for (j = 0; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
而对于外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次。所以这段代码的时间复杂度为O(n²)。
如果外循环的循环次数改为了m，时间复杂度就变为O(m x n)。
int i, j;
for(i = 0, i < m; i++)
{
for (j = 0; j < n; j++)
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}
所以我们可以总结得出，**循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数**
那么下面这个循环嵌套，它的时间复杂度是多少呢？
int i, j;
for(i = 0, i < m; i++)
{
for (j = i; j < n; j++) /* 注意j = i 而不是 0/
{
/ 时间复杂度为O(1)的程序步骤序列 */
}
}
由于当i=0时，内循环执行了n次，当i = 1时，执行了n-1次，······当i = n-1时，执行了1次，所以总的执行次数为：
n+(n-1)+(n-2)+···+1=n(n+1)/2 = (n²+n)/2
用推导大O阶的方法，第一条，没有加法常数不予考虑；第二条，只保留最高阶项，因此保留n²/2;第三条，去除这个项相乘的常数，也就是取出1/2,最终这段代码的时间复杂度为O(n²）。
从这个例子，我们也可以得到一个经验，其实理解大O推导不算难，难的是对数列的一些相关运算，这更多的是考察数学知识和能力。