?博客主页：大寄一场.

?系列专栏：数据结构与算法

  ?博客制作不易欢迎各位?点赞+⭐收藏+➕关注

目录

前言

1.什么是数据结构？

2.什么是算法？

3.数据结构和算法的重要性

4.常见的数据结构及算法

一、算法效率的衡量

二、时间复杂度

1. 时间复杂度的定义：

2.大O的渐进表示法

3.小试牛刀

二、空间复杂度

1.空间复杂度的定义：

2.小试牛刀 

三、常见复杂度的对比

前言

在学习数据结构与算法之前我们得先明白以下几点：

1.什么是数据结构？

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合，它涉及到如何组织和存储数据，以便在程序中进行高效的访问和操作。

2.什么是算法？

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

3.数据结构和算法的重要性

1. 高效解决问题：数据结构和算法可以帮助我们更有效地解决各种问题，包括排序、搜索、图形遍历等。通过使用合适的数据结构和算法，我们可以大大提高计算效率，节省时间和空间资源。

2. 可扩展性：随着计算机硬件和软件的发展，我们需要处理的问题变得越来越复杂。数据结构和算法提供了一种可扩展的方法来应对这些挑战，使得我们能够更好地适应不断变化的需求。

3. 优化程序性能：对于需要大量计算的应用程序，优化程序性能至关重要。数据结构和算法可以帮助我们减少不必要的计算，提高程序运行速度，从而提高用户体验。

4. 提高代码质量：使用适当的数据结构和算法可以确保我们的代码更加简洁、易于理解和维护。这有助于提高代码质量，降低出错概率，并为团队协作创造更好的环境。

5. 适用于各种领域：数据结构和算法不仅在计算机科学领域具有重要意义，而且在其他领域也发挥着关键作用。例如，在金融、医疗、物流等领域，高效的数据处理方法同样具有重要价值。

4.常见的数据结构及算法

常见的数据结构包括：

1. 数组(Array):一组相同类型的数据，通过下标访问。
2. 链表(Linked List):由节点组成，每个节点包含数据和指向下一个节点的指针。
3. 栈(Stack):一种后进先出(LIFO)的数据结构，只能在栈顶进行插入和删除操作。
4. 队列(Queue):一种先进先出(FIFO)的数据结构，只能在队尾进行插入操作，在队头进行删除操作。
5. 树(Tree):由节点组成，每个节点包含数据和指向子节点的指针。
6. 图(Graph):由节点和边组成，节点可以有多个相邻节点。

常见的算法包括：

1. 排序算法(Sorting Algorithm):将一组数据按照一定规则进行排序，如冒泡排序、选择排序、插入排序、快速排序等。
2. 查找算法(Search Algorithm):在一个有序的数据集中查找指定的数据，如二分查找、线性查找等。
3. 递归算法(Recursion Algorithm):通过函数自身的调用实现对问题的解决，如斐波那契数列、阶乘等。
4. 动态规划算法(Dynamic Programming Algorithm):通过将问题分解成更小的子问题来解决复杂问题，如背包问题、最长公共子序列等。
5. 贪心算法(Greedy Algorithm):每次选择当前最优解来解决问题，如最小生成树算法、最短路径算法等。

一、算法效率的衡量

那么提到算法效率，我们肯定想知道如何衡量一个算法的好坏？

比如对于以下斐波那契数列：

long long Fib(int N)
{
 if(N < 3)
     return 1;
 return Fib(N-1) + Fib(N-2);
}

斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

 算法的复杂度

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

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

二、时间复杂度

那么我们首先了解一下什么是时间复杂度。

1. 时间复杂度的定义：

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

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

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

2.大O的渐进表示法

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

推导大O阶方法：

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

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

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

另外有些算法的时间复杂度存在最好、平均和最坏情况：

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

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

• 最好情况：1次找到
• 最坏情况：N次找到
• 平均情况：N/2次找到

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

那么光说理论肯定不好理解，那么我们牛刀小试一下：

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
", count);
}

        操作执行了2N+10次->O(2n+10)；

        通过推导大O阶方法->时间复杂度为 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
", count);
}

        操作执行了M+N次，有两个未知数M和N，

        若M>N,则O（M）;

        若M<N,则O（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
", count);
}

         操作执行了10次->O(10)

         通过推导大O阶方法，常数的时间复杂度为 O(1)

实例4:

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

char *strchr(const char *str, int c) {
    for (; *str != c; str++) {
        
    }
    return (char *)str;
}

     

        最好1次->O(1)

        最坏N次->O(N)

        故时间复杂度为 O(N)

实例5:

// 计算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;
    }
}

        最好N次->O(N)

        最坏(N*(N+1)/2次->O((N*(N+1)/2)     

        故时间复杂度为 O(N^2)

实例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;
}

最好1次，

最坏log2（n)次，

时间复杂度为 O(logN)

第几次查询	剩余待查询元素数量
1	N/2
2	N/(2^2)
3	N/(2^3)
…	…
N	N/(2^N)

ps:为何是logN 而不是log2 (N)

假如有logaB（a为底数），由换底公式可得：

logcA（c为底数）为常数，

由O的运算规则"O( C × f(N) )=O( f(N ) )，

其中C是一个正的常数

得O（logaB）=O（logcB）

可知算法的时间复杂度与不同底数只有常数的关系，均可以省略自然可以用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);
}

通过计算分析发现基本操作递归了2^N次，时间复杂度为O(2^N)。（建议画图递归栈帧的二叉树讲解）

二、空间复杂度

1.空间复杂度的定义：

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

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

2.小试牛刀 

实例1：

// 计算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)

实例2：

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
 if(n==0)
      return NULL;
​
 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i <= n ; ++i)
 {
     fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
​
 return fibArray;
}

        动态开辟了N个空间，空间复杂度为 O(N)

实例3：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
 if(N == 0)
     return 1;
​
    return Fac(N-1)*N;
}

        递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

三、常见复杂度的对比