=======================
什么是算法
算法表示决绝特定问题的求解步骤，由一个或多个操作组成。
算法的特性
输入输出、有穷性、确定性、可行性。
输入输出： 不一定有输入但必须有输出
有穷性 造成死循环的代码不是算法
确定性 算法的每一个步骤都有确定的含义，无需存在多余的步骤。
可行性 算法的每一步都必须在计算机上运行
算法的时间复杂度
公式:
±----------------------------------±----------------------------------+
| 1 | T(n) = O(f(n)) |
±----------------------------------±----------------------------------+
表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。f（n）表示算法的工作量。
也就是说随着n的增大，T(n)增长最慢的算法为最优算法。
推导大O阶
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与整个项相乘的常数。
常数阶
±----------------------------------±----------------------------------+
| 1 | int sum = 0, n=100; |
| 2 | sum = (1+n)*n/2; |
| 3 | printf(“%d”,sum); |
±----------------------------------±----------------------------------+
这里执行了3次，所以f(n)=3。
通过f(n)=3计算出大O阶：
-
把常数项3改为1.
f(n) = 1。由于没有最高阶项，所以时间复杂度为0(1)。
然后假设
sum=(1+n)*n/2这条语句有10句：
那么f(n) = 12，最后推导的结果还是0(1)类似这种执行时间恒定，时间复杂度为0(1)的又叫做常数阶
线性阶
算法中带有循环结构部分的称为线性阶。它的时间复杂度呈线性增长。
对数阶
±----------------------------------±----------------------------------+
| 1 | int count = 1; |
| 2 | while(count < n) |
| 3 | { |
| 4 | count = count * 2; |
| 5 | } |
±----------------------------------±----------------------------------+
它的时间复杂度与上例中的2有关，也与n有关。
此例中常数为2，我们可以得到
$$2^x = n$$
或者
$$x=log_2 n$$
所以对数阶的时间复杂度为O(logn)
平方阶
±----------------------------------±----------------------------------+
| 1 | int i,j; |
| 2 | for (i = 0; i<n; i++){ |
| 3 | for(j=0; j<n;j++){ |
| 4 | |
| 5 | }} |
±----------------------------------±----------------------------------+
这是一个线性阶内嵌在另外一个线性阶中。
当i=0时，它执行了n此，当i=1时，执行了n-1次 …
当i=n-1时，执行了1次。
总的执行次数为:
n + (n-1) + (n-2) … +1 =
$$\frac{n(n+1)}{2}$$
=
$$\frac {n^2} 2 + \frac n 2$$
以最终推导的公式：
$$\frac {n^2} 2 + \frac n 2$$
来计算
按照第二步 去除加号中的常数：
$$\frac n 2$$
保留最高阶：
$$\frac {n^2} 2$$
然后按照第三步去除相乘的常数，也就是去除1/2。最终得到的时间复杂度为：
$$O(n^2)$$
常用的时间复杂度
|执行次数函数|阶|非正式术语|
|—|—|—|
|12|O(1)|常数阶|
|2n+3|O(n)|线性阶|
|3n^2+2n+1|O(n^2)|平方阶|
|5log2n+20|O(logn)|对数阶|
|2n+3nlog2n+19|O(nlogn)|nlogn阶|
|6n^3+2n^2+3n+4|O(n^3)|立方阶|
|2^n|O(2^n)|指数阶|