数据结构——算法的时间复杂度

🌇个人主页：_麦麦_

📚今日名言：生命中曾经有过的所有灿烂，都终究需要用寂寞来偿还。——《百年孤独》

目录

一、前言

        小伙伴们好呀，今天为大家带来的是算法的相关知识，主要围绕算法的效率和时间复杂度并伴有一定的题目练习，希望能够为读者们带来一定的收获。

二、正文

        1.算法效率

                1.1如何衡量一个算法的好坏

        相信在座的小伙伴们一定见识了许多题目，也一定想出了相应的解决方案。不可否认的是，在面对同一道题目，同一个需求，不同的人也会写出不同的解决方案，那么到底如何如何评判这些解决方案的好坏呢？

        有的小伙伴可能会说这还不简单嘛，之间看谁的算法跑的快，也就是依据时间效率的高低来评判算法的好坏。不过在实际中，由于算法的运行环境不同，例如在不同的设备上同一算法的时间效率都可能是不一样的，更遑论是不同的算法了。显然，用时间效率来衡量一个算法的好坏是不可能的，那么有什么更好的方法呢？

                1.2算法的复杂度

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

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

        2. 时间复杂度

                2.1时间复杂度的概念

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

        即：找到某条基本语句与问题规模N之间的数学表达式，就是算出来该算法的时间复杂度。

        说了这么多，纸上得来终觉浅，下面给小伙伴们举一些计算时间复杂度的例子，帮助大家更好地理解时间复杂度这一概念。

//请计算一下Func1中++count语句总共执行了多少次？
void Func1(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);
}

         看过上面的代码，相信你们一定能够很轻易的算出Fun1执行的基本操作次数是一个关于N的函数：F(N)=N²+2N+10

●N=10          F(N)=130

●N=100        F(N)=10210

●N=1000      F(N)=1002010

注：实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，具体操作是怎样呢，接下来我们引入大O的渐进表达法

                2.2大O的渐进表示法

大O符号：适用于描述函数渐进行为的数学符号

推导大O阶方法：

1.用常数1取代运行时间中所有的加法常数

2.在修改后的运行次数函数中，只保留最高阶项

3.如果最高阶项存在且不为1，则去除与这个项目相乘的常数，得到的结果就是大O阶

        因此，在上面的例子中，采取大O的渐进表示法以后，Fun1的时间复杂度为：F（N²）

●N=10          F(N)=130

●N=100        F(N)=10210

●N=1000      F(N)=1002010

        通过上面我们会发现大O的渐进表示法去掉了哪些对结果影响不大的项，简洁明了的表示出了执行次数。不过随着算法的深入，我们会发现有些算法的时间复杂度并不是唯一确定的，而是存在着最好、平均和最坏情况： 

●最坏情况：任意输入规模的最大运行次数（上界）

●平均情况：任意输入规模的期望运行次数

●最好情况：任意输入闺蜜的最小运行次数（下界）

        例如：在一个长度为N的数组中搜查一个数据x

●最坏情况：N次找到

●平均情况：N/2次找到

●最好情况：1次找到

        在实际中一般关注的是算法的最坏运行情况，所以数组中搜索数据的时间复杂度为O（N）。

         之所以以最坏情况来作为算法的时间复杂度，在这里其实是应用了信息学中的“预期管理”，就好比情人节那天，你要与你的男/女朋友约会，而约会时间可能是17点、18点、19点，那么相信大多数的人都会选择19点，如果刚刚好19点来就挺守时的嘛，如果早来，还可以提前准备，给他/她一些惊喜。相反，如果你将约定时间定位17点或者18点，一旦无法在约定时间前来，就是放鸽子了，可能会产生意料之外的各种特殊情况……

        因此，采取最坏情况作为时间复杂度的算法跑起来只有惊喜和预期，不可能比预期更坏。

                2.3 常见时间复杂度计算举例

●实例1

// 计算Func2的时间复杂度
void Func2(int N)
{
 int count = 0;
 for (int k = 0; k < 2 * N ; ++ k)
 {
 ++count;
 }
 int M = 10;
 while (M--)
 {
 ++count;
 }
 printf("%d\n", count);
}

       通过计算，F（N）=2N+10，因此该算法的时间复杂度为O（N） 

●实例2

// 计算Func3的时间复杂度
void Func3(int N, int M)
{
 int count = 0;
 for (int k = 0; k < M; ++ k)
 {
 ++count;
 }
 for (int k = 0; k < N ; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}

        通过计算，在一般情况下，也就是M和N均为未知数的情况下，F（N）=M+N，所以O（N）=M+N 

注：如果题目中说M远大于N，那么O(N)=M

●实例3

// 计算Func4的时间复杂度
void Func4(int N)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}

        通过计算我们发现无论N取何值，F（N）始终等于一个常数也就是 ，根据 大O阶方法的一条，用1来代表所有常数，也就是该时间复杂度为O（1）

●实例4

// 计算strchr的时间复杂度
const char * strchr ( const char * str, int character );

        对库函数有过一定了解的同学一定知道“strchr”这个函数会依次对str指针+1，如果找到目的字符便会返回其指针，找不到便会返回空指针。而这里就会存在最好、最坏和平均情况，因此该函数的时间复杂度为O(N)

注：未指定未知数的情况下默认为N

●实例5

// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{
 assert(a);
 for (size_t end = n; end > 0; --end)
 {
     for (size_t i = 1; i < end; ++i)
     {
         if (a[i-1] > a[i])
         {
             Swap(&a[i-1], &a[i]);
             exchange = 1;
         }
     }
 }
}

        最好情况：O(N)——无须排序

        最坏情况：O(N²)——全部交换

相信最坏情况的时间复杂度大家应该可以很轻易的想出来，但是最坏情况可能就有些复杂了。我们都知道冒泡排序共有两个流程，一个是趟数，一个是每趟交换的次数。那么时间复杂度就是总的交换次数。在看过博主之前推文对冒泡排序的小伙伴应该十分了解在冒泡排序最坏的情况下中，首趟交换的次数是最多的，为元素个数减，即N-1，之后虽趟数的增加，每趟交换的次数以1的速度递减。那么总的趟数计算的话其实就是一个高中很简单的等差数列求和，即（首项+尾项）*项数/2，代入N-1，可得F(N)=N*(N-1)/2，所以O(N)=N²。

 ●实例6

// 计算BinarySearch的时间复杂度——二分查找
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(1)

        最坏情况下，就是将数组不断二分直至长度为1为止，此时可能找到目标值也可能没有目标值。因此F(N)=log以2为底的对数，大部分情况下简写为logN，所以O(N)=logN。

●实例7

// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
    if (0 == N)
        return 1;

    return Fac(N - 1) * N;
}

         有时候，我们可能在脑海中无法形象的，一下子的得出时间复杂度，这时候就可以通过画图来帮助自己理清思路，进而得出时间复杂度。通过上图，我们可以发现在最坏的情况下基本操作进行了N次，时间复杂度为O(N)

● 实例8

// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

        我们发现这其实是一个等比数列求和，虽然右边有一些数提前递归结束，但是随着N的增大，是可以忽略不计的。因此该时间复杂度为O(2^N) 

三、结语

         到此为止，关于算法的时间复杂度的学习就告一段落了。

         关注我 _麦麦_分享更多干货：_麦麦_的博客_CSDN博客-领域博主
         大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！