时间复杂度和空间复杂度_常数级空间

一开始接触数据结构，不可避免的要了解如何计算一个算法的时间复杂度和空间复杂度，也许你之前听过，但是并没有深入了解的话，那么就可以和我一起来了解下哦。。。

本篇文章讲的主要内容：
1.时间复杂度
2.空间复杂度
3.两个小例子来深入理解（使用递归或非递归时的）时间复杂度和空间复杂度。

如何衡量一个算法的好与坏？

算法的时间复杂度和空间复杂度统称为算法的复杂度。

空间复杂度是指当前问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所占用的存储空间也以某种单位由1增加到S(n)———>则称此算法的空间复杂度为S(n)。

时间复杂度是指当前问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所耗费的时间也以某种单位由1增加到T(n)—–》则称此算法的时间复杂度为T(n)。

时间复杂度的分析方法：

1、时间复杂度就是函数中基本操作所执行的次数
2、一般默认的是最坏时间复杂度，即分析最坏情况下所能执行的次数
3、忽略掉常数项及系数，保留对增长因子影响最大的一部分。
4、关注运行时间的增长趋势，关注函数式中增长最快的表达式，忽略系数
5、计算时间复杂度是估算随着n的增长函数执行次数的增长趋势
6、递归算法的时间复杂度为：递归总次数 * 每次递归中基本操作所执行的次数

时间复杂度实际就是一个函数，该函数计算的是执行基本操作的次数。

算法分析的分类：

1. 最坏情况：任意输入规模的最大运行次数。(上界)
2. 平均情况：任意输入规模的期望运行次数。
3. 最好情况：任意输入规模的最小运行次数，通常最好情况不会出现。(下界)
1
2
3

在实际中我们通常考量的是算法的最坏运行情况。也就是说对于任意输入规模N，算法的最长运行时间，理由如下：

1. 一个算法的最坏情况的运行时间是在任意输入下的运行时间上界。
2. 对于某些算法，最坏的情况出现的较为频繁。
3. 大体上看，平均情况与最坏情况一样差。
1
2
3

算法分析要保持大局观：

1. 忽略掉那些的常数。
2. 关注运行时间的增长趋势(增长因子)，关注函数式中增长最快的表达式。
1
2

一般算法O(n)计算方法：
1、用常数1取代运行时间中的所有加法常数
2、在修改后的运行次数函数中，只保留最高阶项
3、如果最高阶项系数存在且不是1，则去除与这个项相乘的常数。

空间复杂度：
算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。

S(n)=O(f(n)) 若算法执行时所需要的辅助空间相对于输入数据量n而言是一个常数，则称这个算法的辅助空间为O(1)。

递归算法的空间复杂度：递归深度N*每次递归所要的辅助空间， 如果每次递归所需的辅助空间是常数，则递归的空间复杂度是 O(N).

那么递归算法的时间复杂度和空间复杂度该如何计算呢？
【递归算法的时间复杂度计算】
递归算法的时间复杂度为递归总次数*每次递归次数。
【递归算法的空间复杂度计算】
递归算法的空间复杂度为递归深度*每次递归所创建的对象个数。

示例1：
下面我们一起来分析一下二分查找(使用递归算法和非递归算法)的时间复杂度和空间复杂度。
//非递归方法

int BinarySearch(int* array, int len, int data)
{
    int left = 0;
    int right = len - 1;

    while (left <= right)
    {
        int middle = (left & right) + ((left ^ right) >> 1);
        if (data > array[middle])
        {
            left = middle + 1;
        }
        else if (data < array[middle])
        {
            right = middle - 1;
        }
        else
        {
            return middle;
        }
    }
    return -1;
}

int main()
{
    int array[] = { 1, 2, 3, 6, 7, 8, 9, 10 };
    int ret = BinarySearch(array, sizeof(array)/sizeof(int), 7);//4
    cout << ret << endl;
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

由上图可以得出：
在最坏的情况下，二分查找需要查找的次数为log2N(2为底数，N为对数)次，也就是上述程序中循环执行的次数，即就是二分查找的时间复杂度为O(log2N(2为底数，N为对数）)。
可以很明显的看出，整个程序中所新创建变量个数为常数级的，所以空间复杂度即就是O(1)。

总结下：
对于二分查找（非递归）的时间复杂度和空间复杂度：
循环的基本次数是log2 N，所以:
时间复杂度是O(log2 N)（2为底数，N为对数）;
由于辅助空间是常数级别的所以：
空间复杂度是O(1);

递归算法：

int BinarySearch(int* array, int left, int right, int data)
{
if (left > right)//递归出口
{
return -1;
}
int middle = (left & right) + ((left ^ right) >> 1);

if (data > array[middle])
{
left = middle + 1;
BinarySearch(array, left, right, data);
}
else if (data < array[middle])
{
right = middle - 1;
BinarySearch(array, left, right, data);
}
else
{
return middle;
}
}

int main()
{
int array[] = { 1, 2, 3, 6, 7, 8, 9, 10 };
int ret = BinarySearch(array,0, sizeof(array) / sizeof(int) - 1, 7);//4
cout << ret << endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

总结下：
对于二分查找（递归）的时间复杂度和空间复杂度。
递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：
时间复杂度:O(log2 N)//2为底数，N为对数
空间复杂度：O(log2 N )

先来了解下二叉树的节点个数和树的层数的关系（下面会用到的哦）：

完全二叉树的时间复杂度为节点的总个数（h = log2 N(2为底数，N为对数) ）。

二叉树的层数为h，那么这个二叉树的总节点个数就为2^h -1。

示例2：根据上述结论来看斐波那契数列的递归算法和非递归算法的时间复杂度和空间复杂度：
斐波那契数列：

①递归解法：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include<cassert>
int fib1(int n)
{
if (n == 1 || n == 2)
return 1;
return fib1(n - 1) + fib1(n - 2);
}

int main()
{
cout << fib1(20) << endl;
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

②非递归的：

//非递归形式的斐波那契数列
//用一个数组作为辅助的空间
//效率较高
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

int Fib(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
int first = 1;
int second = 1;
int ret = 0;
for (int i = 2; i < n; i++)
{
ret = first + second;
first = second;
second = ret;
}
return ret;
}

void Test1()
{
int ret = Fib(20);
cout << ret << endl;
}

int main()
{
Test1();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结下：循环的基本次数是n-1，所用的辅助空间是常数级别的：
非递归算法的时间复杂度：O(n)
非递归算法的空间复杂度：O(1)

常用的时间复杂度有以下七种，
算法时间复杂度依次增加：
O(1)常数型 < O(log2 n)对数型 < O(n)线性型 < O(nlog2n)二维型 < O(n^2)平方型 < O(n^3)立方型 < O(2^n)指数型.