【数据结构】复杂度详解

这篇具有很好参考价值的文章主要介绍了【数据结构】复杂度详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

（一）算法的复杂度

（二）时间复杂度

（1）练笔+解释：

i，示例1

ii，示例2

iii，二分查找

iv，斐波那契

（三）空间复杂度

练笔+解释：

i，冒泡排序

ii，斐波那契

（四）常见复杂度对比：

正文开始：

我们为什么要讨论复杂度呢？因为复杂度能够衡量一个程序算法的好坏，关乎你写的程序能否在你的这台计算机上执行，如果能够执行，执行的效率又怎么样？如果程序的空间复杂度太大，可能根本无法在计算机上执行，因为计算机没有足够大的空间；如果时间复杂度太大，那么在有限的时间内可能根本没办法得到答案；因此，讨论复杂度是必要的。

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

（一）算法的复杂度

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

（二）时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。（来自 <什么是P问题、NP问题和NPC问题 | Matrix67: The Aha Moments>）

我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
有些算法的时间复杂度存在最好、平均和最坏情况：

        最坏情况：任意输入规模的最大运行次数(上界)
        平均情况：任意输入规模的期望运行次数
        最好情况：任意输入规模的最小运行次数(下界)

        在实际中一般情况关注的是算法的最坏运行情况。

（1）练笔+解释：

i，示例1
//在这个函数中，count++一共被执行了多少次？
void Fun_example1(int N)
{
    int count = 0;

    for (int i = 0; i < N ; ++ i)
    {
        for (int j = 0; j < N ; ++ j)
        {
            ++count;
        }
    }

    for (int k = 0; k < 2 * N ; ++ k)
    {
        ++count;
    }

    int M = 10;

    while (M--)
    {
        ++count;
    }

    printf("%d\n", count);
}
在Fun_example1函数中，count++语句一共被执行了F(N)=N^2+2*N+10次；随着N的增大，N^2对时间复杂度的影响逐渐凸显，因此N^2是最高阶项，保留最高结项得到Fun_example1的时间复杂度为O(N^2)。

ii，示例2

//这个函数呢，count++被执行了多少次？
void Func_example2(int N)
{
    int count = 0;

    for (int k = 0; k < 2 * N ; ++ k)
    {
        ++count;
    }

    int M = 10;

    while (M--)
    {
        ++count;
    }

    printf("%d\n", count);
}
在Fun_example2函数中，count++语句一共被执行了F(N)=2*N+10次；随着N的增大，2*N对时间复杂度的影响逐渐凸显，因此2*N是最高阶项，保留最高阶项并去掉最高阶项的系数得到Fun_example1的时间复杂度为O(N)。

iii，二分查找

//二分查找的时间复杂度是多少？
int BinarySearch(int* a, int n, int x)
{
    assert(a);

    int begin = 0;
    int end = n-1;

    // [begin, end]：begin和end是左闭右闭区间，因此有=号
    while (begin <= end)
    {
    int mid = begin + ((end-begin)>>1);

    if (a[mid] < x)
        begin = mid+1;
    else if (a[mid] > x)
        end = mid-1;
    else
        return mid;
    }
    return -1;
}
二分查找的基本操作最好执行一次，最坏执行O(logN)次,时间复杂度按照最坏的算，是O(logN)。（在算法分析中，如果没有特殊说明，logN表示以二为底N的对数）

iv，斐波那契

斐波那契

//你能计算斐波那契的时间复杂度吗？
long long Fib(size_t N)
{
    if(N < 3)
        return 1;

    return Fib(N-1) + Fib(N-2);
}

当n=3时，递归展开图如图：

当n=4，递归展开图如图：

当n=5，递归展开图如图：

我在作图的时候其实是挺方便的，做n=5的图只需将n=4与n=3的图放在下边即可，这就是复用。但是计算机在计算的时候不会像我这样复用已经计算出来的结果，对于递归的每一层，计算机都会从最开始的第一层算到这一层。换句话说：我可以n的值为3和4的图链接起来，形成n=5的图；计算机在计算n=5的递归值时，计算机不会将n的值为3和4的递归结果加起来得到5，而是从n=1或2算到n=3的结果，在同样算到n=4的结果，在这之后再相加得到n=5的值。

（这预示着斐波那契递归算法的效率是极低的！）

随着n的增大：

递归树越来越接近满二叉树，它比满二叉树缺少了一部分：

假设递归树的高度为h，那么整个递归过程的时间复杂度可以近似表示为每一层的节点数乘以高度h。因此，时间复杂度可以表示为：

T(n) = O(2^0) + O(2^1) + O(2^2) + ... + O(2^h)

由于每一层的节点数是逐渐减少的，可以将上述等式转化为以下形式：

T(n) ≤ O(2^0) + O(2^1) + O(2^2) + ... + O(2^(h-1)) + O(2^h)

（你也可以对等比数列求和）

我们知道，对于任意正整数k，2^k ≥ k。因此，上述等式可以进一步简化为：

T(n) ≤ O(h2^h)

由于递归树的高度h与输入规模n之间存在一个关系h = O(log n)，因此可以将上述等式进一步简化为：

T(n) ≤ O(log n * 2^log n) = O(n log n)

所以，使用递归方式求解斐波那契数列的时间复杂度可以表示为O(n log n)。

（三）空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

空间复杂度与时间复杂度不同的是：

空间的销毁是归还使用权，操作系统仍然可以使用，因此时间是逐渐积累的，是一去不复返的；而空间是可以重复利用的。

练笔+解释：

i，冒泡排序

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);

    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;

        for (size_t i = 1; i < end; ++i)
        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }

        if (exchange == 0)

        break;
    }
}

开辟了常数个额外空间，所以空间复杂度为O(1)。

ii，斐波那契

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
    if(N == 0)
        return 1;
    return Fac(N-1)*N;
}
递归调用了N次，开辟每个栈帧开辟了常数个空间，空间复杂度为O(N)。

而斐波那契的空间是动态的，既有开辟又有释放，按照最大的占用空间算，空间复杂度为O(N)。