版本记录
| 版本号 | 时间 |
|---|---|
| V1.0 | 2018.09.14 |
前言
关于算法学习有很多很基础的概念和理论，我们不需要强行记忆但是一定要理解明白和说的出来，这个专题就是专门进行有关算法基本内容的一些解析。
时间复杂度
首先一起来理解一下时间复杂度。
个人理解：时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。
官方解释：计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
常见的时间复杂度
常见的时间复杂度主要有下面几种：
- 常数阶O(1)
- 对数阶O(log2 n)
- 线性阶O(n)
- 线性对数阶O(n log2 n)
- 平方阶O(n^2)
- 立方阶O(n^3)
- k次方阶O(n^K)
- 指数阶O(2^n)
随着n的不断增大，时间复杂度不断增大，算法花费时间越多。
常见的算法时间复杂度由小到大依次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)
计算方法
- 选取相对增长最高或者说最快的项（对应的就是函数图像中增长最快的函数，比如3次方就比2次方的增长的快）。
- 最高项系数是都化为1 。
- 若是常数的话，因为执行语句次数固定，比如就是执行100次，那么就用O（1）表示 。
下面看几个计算方法示例。
1. O（1）
当算法执行固定的次数（即使有成千上万的数量级），和n没有关系的时候，那么复杂度就是O（1）。例如：
int x = 1;
while (x <= 10000)
{
x++;
}
这里，while里面的代码就执行10000次，看着很多，但是对于机器的主频来说真不算什么，这个和n没有任何关系，就是一个固定的常数。
2. O（n^2)
这个一般是和循环嵌套有关系，而且复杂度会随着n的改变而变化。例如：
for (i = 0; i < n; i ++)
{
for (j = 0; j < n; j ++)
{
;
}
}
该算法for循环，最外层循环每执行一次，内层循环都要执行n次，执行次数是根据n所决定的，时间复杂度是O（n^2）。
3. O(n)
这个很明显，就是时间复杂度是n线性相关的，例如：
for (i = 0; i < n; i ++)
{
//执行语句
}
这个for循环执行次数与n有关，并且是线性的，所以复杂度就是O(n)。
4. O(log2 n)
下面看一下这个二分查找算法。
二分查找算法 - 非递归
int BinarySearch(int arr[], int len, int num)
{
assert(arr);
int left = 0;
int right = len - 1;
int mid;
while (left <= right)
{
mid = left + (right - left) / 2;
if (num > arr[mid])
{
left = mid + 1;
}
else if (num < arr[mid])
{
right = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
这个时间复杂度为O（log2 n） ，因为变量值创建一次，所以空间复杂度为O（1）。
二分查找算法 - 递归
int BinarySearchRecursion(int arr[5], int lef, int rig,int aim)
{
int mid = lef + (rig - lef) / 2;
if (lef <= rig)
{
if (aim < arr[mid])
{
rig = mid - 1;
BinarySearchRecursion(arr, lef, rig, aim);
}
else if (arr[mid] < aim)
{
lef = mid + 1;
BinarySearchRecursion(arr, lef, rig, aim);
}
else if (aim == arr[mid])
{
return mid;
}
}
else
return -1;
}
这个时间复杂度就是O（log2 n） ，每进行一次递归都会创建变量，所以空间复杂度为O（log2 n）。
可能有人想知道这个时间复杂度O（log2 n）是怎么计算出来的？
| 第几次查询 | 剩余待查询元素数量 |
|---|---|
| 1 | N/2 |
| 2 | N/(2^2) |
| 3 | N/(2^3) |
| ... | ... |
| K | N/(2^K) |
从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是
N/(2^K)=1 => N=2^K => K=log2N
所以二分查找的时间复杂度为O(log2N)。
5. O(2^n)
下面看一下这个斐波那契数列（Fibonacci sequence），又称黄金分割数列。
int FeiBoNaCciRecursion(int num)
{
if (num < 0)
return -1;
if (num <= 2 && num > 0)
return 1;
else
return FeiBoNaCciRecursion(num - 1) + FeiBoNaCciRecursion(num - 2);
}
int main()
{
int n;
int result;
printf("Input n\n");
scanf("%d", &n);
result = FeiBoNaCciRecursion(n);
if (result == -1)
printf("Input Error!\n");
else
printf("Result is %d\n", result);
return 0;
}
在这种递归情况下的时间复杂度就是O(2^n)。
在分析算法的时间复杂度的时候，非递归使用的是for循环，其时间复杂度为O(n)。而递归的时间复杂度则比较复杂，其分析出来为O(2^n)。这里需要说明的就是，非递归的for循环其时间复杂度O(n)虽然很小，但是其空间复杂度却比递归调用差得多。因为，循环在每次循环的时候，都把相应的数值保存下来了，而递归调用却不会保存相应的数值。
算法复杂度练习
下面我们就做一些练习计算算法复杂度。
1. 例1
int main(int argc, const char * argv[])
{
int number = 0;
int n = 999;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++){
for(int k = j; k <= j; k++){
number ++;
}
}
}
return 0;
}
我们抽象出来公式然后进行近似计算，如下所示：
那么这个算法的时间复杂度就是O（n^3)。
2. 例2
int main(int argc, const char * argv[])
{
int n = 6000;
int i = 1;
while(i <= n){
i = i * 3;
}
printf("i = %d\n", i);
return 0;
}
下面看一下上面的时间复杂的，这个可以看做是进行迭代的。假设执行了k次之后，才会停止，那么就有i = n,此时i = 3*3*3*3..........*1 = 3^k，因为这是一个递归，所以有3^k = n,两边取对数，那么就有k = log n(底数为3)，此时就是T(n) = O(log n)。
3. 例3
int main(int argc, const char * argv[])
{
int n = 10;
int i = 0, j = 1;
while(i + j <= n){
printf("i + j = %d\n", i + j);
if (i > j) {
j++;
}
else {
i++;
}
}
return 0;
}
每次循环，i + j的值都会增加1，一共循环了n次，所以时间复杂度就是O(n)，可以看一下输出：
i + j = 1
i + j = 2
i + j = 3
i + j = 4
i + j = 5
i + j = 6
i + j = 7
i + j = 8
i + j = 9
i + j = 10
4. 例4
int main(int argc, const char * argv[])
{
int x = 91, y = 100;
while (y > 0) {
if (x > 100) {
x -= 10;
y--;
}
else {
x++;
}
}
return 0;
}
这里可以看见，总共循环了很多次，但是我们没有看见和n有关系，也就是说和n是无关的，就是一个常数阶的函数，时间复杂度为O(1)。
参考文章
1. 时间复杂度和空间复杂度的简单讲解
2. 算法 二分查找的时间复杂度为O(log2N)的原因推理
3. 复杂度分析之斐波那契数列
后记
本篇主要讲述了算法的时间复杂度分析，感兴趣的给个赞或者关注~~~
