《数据结构初阶》【时间复杂度 + 空间复杂度】

前言：

hi~，正在看这篇博客的小伙伴，如果你之前看过博主的博客的话，此时内心应该不禁感叹：这博主是不是又打算挖个坑就跑？，（因为这个博主之前挖过：《C语言系列》、《算法基础》、《算法精讲》这些坑，其中《C语言系列》的坑都长草了吧？🤔，今天又打算再一个新坑吗？）

---

博主先在这里声明一下：博主是一个有头有尾有始有终的人，
"你们要相信我！每一个坑都是真爱！只是它们……在等一个合适的时机成熟！🫠
例如：《C语言系列》还剩下：“复合结构体 + 文件操作” 这两部分的内容的没有更新，博主预估想完结《C语言系列》至少还需要4篇博客，由于博主现在的重心不是学习C语言，所以可能会鸽很久 （在这个以视频学习为主的时代，也不知道有没有人看），不过博主的博客当笔记来看是最好的，因为内容较全，拿来复习是很不错的😍
而《算法基础》、《算法精讲》接下来可能就是偶尔更一下了，
《数据结构初阶》将是博主接下来持续更新的内容了，博客内容主要划分为：数据结构的介绍 + 数据结构的实现 + 数据结构的OJ练习

---

祝愿：希望《数据结构初阶》系列的内容可以帮助到大家~
（如果没帮到也不要紧，至少你收获了 “原来还有人比我更菜” 的心理安慰😂）

-----------------------------------------

1. 什么是数据结构？

既然是学习 《数据结构》 这门课程，那么我们要思考的第一个问题无疑就是： 什么是数据结构？

数据结构：是计算机科学中用于组织、存储和管理数据的一种 方式

• 用于实现高效的数据访问、修改和操作

• 它定义了数据元素之间的 逻辑关系、存储方式 以及 相关的操作（如：增删查改），是算法设计和程序优化的基础

2. 什么是算法？

俗话说的好：数据结构与算法不分家（其实是我说的）

那么接下来也一并见见的他的妻子（😂）

算法 ：是解决特定问题的一系列明确、有限的 步骤

• 用于对数据进行计算、处理或自动化决策。
• 它是计算机程序的逻辑核心，决定了程序的效率和正确性。

-----------------------------------------

算法的时间复杂度和空间复杂度

1. 为什么要引入时间复杂度和空间复杂度？

疑问：算法种类繁多，千奇百怪，面对具体的问题我们要选择什么样的算法才是最好的选择呢？或者也可以理解为：看到一种算法我们怎么知道它是好还是坏呢？

示例：比如对于下面这个求斐波那契数列的算法：

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

思考：这种递归实现的算法非常的简洁，但是简洁就一定好吗？换句话说：难道简洁是衡量一个算法的好坏的标准吗？如果不是那我们要使用什么来衡量一个算法的好与坏呢？

---

回答：我们可以使用下面的两把 “尺子” 来衡量解决这个问题的算法中的那个是最好的。

而这两把尺子分别是：时间复杂度和空间复杂度

思考与探究：我们怎么想到了用这两个维度的信息进行衡量一个算法的好坏呢？

---

回答：算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。

因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即：时间复杂度和空间复杂度。

2. 什么是时间复杂度和空间复杂度？

时间复杂度：是衡量算法 运行时间随输入规模 n 增长的变化趋势的指标。

• 它不计算具体的执行时间，而是分析算法执行的基本操作次数的增长规律，并用数学符号（如：大O表示法）描述其渐进上界

---

空间复杂度：是衡量算法 运行所使用的内存空间随输入规模 n 增长的变化趋势的指标。

• 它不计算具体的内存占用大小，而是分析算法运行过程中所需的额外存储空间的增长规律，空间复杂度也用大O表示法（Big-O Notation）其渐进上界

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等……)在编译期间已经确定好了。

因此：空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

---

所以：这里说的直白一点就是时间复杂度和空间复杂度其实你也可以理解为：他们俩其实就是一个函数，具体一点就是一个

• 时间复杂度：运行时间(y) 和 输入规模 (n) 的函数
• 空间复杂度：运行所使用的内存空间 (y) 和 输入规模 (n) 的函数

只不过函数是什么类型的函数我们并不清楚？

3. 常见的时间复杂度类型有哪些？

也可以理解为函数的类型：

4. 常见的空间复杂度类型有哪些？

5. 为什么选择使用时间复杂度和空间复杂度？

疑问：如果想要计算时间复杂度和空间复杂度的话，我们直接找一台计算机，运行这两个算法，并监控记录它们的运行时间和内存占用情况，这样不就比较出这两种算法谁好谁差了吗？有必要使用一个函数进行表示吗？

---

直接原因：直接运行测试的局限性

(1) 硬件依赖性

• 不同设备性能差异：同一算法在低配手机和高性能服务器上运行时间可能差几十倍，无法客观比较算法优劣。
• 后台进程干扰：计算机同时运行的其他程序（如杀毒软件、浏览器）会占用资源，影响测试结果。

(2) 数据规模的影响

• 小规模数据无法反映趋势：
  • 当输入规模 $n$ 很小时，$O(n^2)$ 的算法可能比 $O(n\log n)$ 更快（因为常数项或低阶项主导）
  • 但当 $n$ 增长到百万级时，$O(n^2)$ 的算法会变得极慢，而实际测试可能无法覆盖所有规模

(3) 编程语言和实现的差异

• 语言特性影响：Python 的列表操作比 C++ 的向量慢，但这不代表算法本身效率低。
• 代码优化干扰：编译器优化（如：循环展开、内联函数）可能让同一算法的不同实现表现迥异。

(4) 测试成本高

• 穷举所有输入不现实：算法可能在某些特殊输入下表现极差（如：快速排序的最坏情况 $O(n^2)$ ，但测试时未必能覆盖到。

实际测试 vs 复杂度分析的关系：

6. 我们要怎么表示时间复杂度和空间复杂度？

疑问：时间复杂度分析算法执行的基本操作次数，这这……好分析吗？这应该会很麻烦吧？真的可以用笔和纸就算出来了吗？

---

回答：实际中我们计算时间复杂度时，我们其实并不需要要计算精确的执行次数，而只需要计算大概执行次数，因为这里我们使用的是：大O的渐进表示法

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

---

你现在心里一定在想：说的好像很有道理，但是事实真的如你所说的只用计算一个渐进的值就可以吗？

示例：

// 请计算一下Func1中count++语句总共执行了多少次？
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			count++;
		}
	}//执行了N^2次的count++语句

	for (int k = 0; k < 2 * N; ++k)
	{
		count++;
	}//执行了2N次的count++语句

	int M = 10;
	while (M--)
	{
		count++;
	}//执行了10次的count++语句

	printf("%d\n", count);
}

第一种方案：使用大O的渐进表示法：时间复杂度为$O(N^2)$

假如：我们的N取下面的不同的值，我们观察一下count++语句都具体执行了多少次？

N = 10 -------- F(N) = 100

N = 100 ------- F(N) = 10000

N = 1000 ----- F(N) = 1000000

---

第二种方案：使用精确计算程序的执行的次数

Func1 执行的基本操作次数 ：（主要分为三部分）

将三部分的 count++ 执行次数相加：
$text总次数=N^2+2N+10$

---

假如：我们的N取下面的不同的值，我们观察一下count++语句都具体执行了多少次？

N = 10 -------- F(N) = 130 （第一部分：100；第二部分：20；第三部分：10）

N = 100 ------- F(N) = 10210 （第一部分：10000；第二部分：200；第三部分：10）

N = 1000 ----- F(N) = 1002010 （第一部分：1000000；第二部分：2000；第三部分：10）

---

通过上面两种分析时间复杂度的方法的比较我们发现：

使用大O的渐进表示法不仅可以快速的计算出一个算法大致的执行的次数，并且计算结果与精确值的量级是一致的（误差不大）

我想大家的心里一定在想：

1. 使用大O的渐进表示法我们只保留了计算出来了最高阶项的值，而直接忽略了低阶项的值，如果哪一天所有的低阶项的值的和已经几乎和高阶项相等了，我看你还怎么忽视？（例如：程序总共执行了1999次：一个高阶项贡献1000次，所有的低阶项贡献999次）（哼🫠）
2. 好就算你有理由说是：“最高阶项的贡献还是比所有的低阶项多”，但是当我的N取得很小呢？（例如：上面的N取1，程序总共执行了13次，一个高阶项贡献1次，所有的低阶项贡献12次）（哈哈😄，看你怎么办）

---

大家的问题真是：夺命两连问啊？，幸好博主早有准备（🐕没有狗头就拿狗来代替吧）

其实大O的渐进表示法可以有以下两种方式得来：

• 直接看程序中执行次数最多的那一部分其他的细枝末节的直接忽略，即：直接锚定高阶项，得到的就是大O的渐进表示法的形式
• 间接通过程序精确的执行次数，来进一步得到大O的渐进表示法的形式
  • 第一步：忽略所有 低次幂项
  • 第二步：忽略 最高次幂的系数

所以的小可爱你的第一问已经被我迎刃而解了，由于还要要忽略 最高次幂的系数，所以对于时间复杂度来说：执行1000次和执行9999次是同一个复杂度的啦~

---

至于第二问的疑问源于：你忽略了一个时间复杂的定义中的一点“是衡量算法 运行时间随输入规模 n 增长的变化趋势的指标

也就是说：其实任何算法在输入规模比较小的时候，程序执行的时间是没什么差异的，你也可以理解为在输入规模很小的时候，它们是一样好的。

因为：CPU的执行速度非常的快，快到即使你的CPU性能再差再差，它每秒也可执行上亿次。

（CPU中有一个概念CPU主频：主频越高，通常意味着CPU的处理速度更快）

---

算法在时间上的差异主要体现在当输入规模不断变大的时候它们的执行时间开始有了不同程度的变慢，即：有的是一下就变慢了，有的则是缓慢变慢了，有的则是没什么明显差别。

7. 时间复杂度分为哪些？

最坏时间复杂度（Worst-Case Time Complexity）：算法在最不利输入情况下的时间增长趋势（上界）

• 作用：保证算法性能的下限，确保任何情况下都不会比这更差

最好时间复杂度（Best-Case Time Complexity）：算法在最理想输入情况下的时间增长趋势（下界）

• 作用：反映算法在最优场景下的潜力，但实际意义有限。

平均时间复杂度（Average-Case Time Complexity）：算法在所有可能输入*的期望时间成本（需假设输入的概率分布）

• 作用：更贴近实际应用场景的综合性能评估。

---

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

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

三者的对比与意义

经典算法示例分析：

1. 快速排序

• 最坏： $O(n^2)$（输入已有序，分区极度不平衡）
• 最好：$O(n\log n)$（每次分区均匀）
• 平均：$O(n\log n)$（随机化输入或随机化分区策略）

2. 二分查找

• 最坏：$O(logn)$（元素不存在或位于两端）
• 最好：$O(1)$（目标元素正好是中间元素）
• 平均：$O(logn)$（假设目标元素等概率分布）

3. 冒泡排序

• 最坏：$O(n^2)$ （输入逆序，需完全比较）
• 最好：$O(n)$（输入已有序，一次遍历即结束）
• 平均：$O(n^2)$（随机排列时仍需多次交换）

-----------------------------------------

常见时间复杂度计算举例

常数阶O(1)

//Func2的时间复杂度
void Func2(int N) 
{
    int count = 0;
    for (int k = 0; k < 100; ++k) // 固定循环100次
    {  
        count++;
    }
    
    printf("%d\n", count);
}

答案：

• 时间复杂度：$O(1)$
• 原因：循环次数固定为100次，与输入规模 $N$ 无关。

对数阶O(nlogn)

//BinarySearch（二分查找）的时间复杂度
int BinarySearch(int* a, int n, int x) 
{
    assert(a);
    int begin = 0;
    int end = n - 1;
    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)$
• 原因：每次迭代将搜索范围缩小一半，最坏情况下需执行 $lo{g}_{2}n$ 次。

线性阶O(n)

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

答案：

• 时间复杂度：$O(n)$
• 原因：主导项是 (2N)。常数项（10次）和系数（2）在渐进分析中忽略。

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

答案：

• 时间复杂度：$O(n)$
• 原因：最坏情况下需遍历整个字符串（长度为 n ）才能找到目标字符或到达结尾。

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

答案：

• 时间复杂度：$O(M+N)$
• 原因：两段循环分别依赖 $M$和 $N$，无法进一步简化。

//阶乘递归 Fac 的时间复杂度
long long Fac(size_t N) 
{
    if (N == 0)  return 1;
    return Fac(N - 1) * N;  // 递归调用N次
}

答案：

• 时间复杂度：$O(n)$
• 原因：递归深度为 $N$，每次递归执行常数时间操作。

平方阶O(n^2)

//BubbleSort（冒泡排序）的时间复杂度
void BubbleSort(int* a, int n) 
{
    assert(a);
    for (size_t end = n; end > 0; --end) // 外层循环n次
    {      
        int exchange = 0;
        for (size_t i = 1; i < end; ++i) // 内层循环最多n-1次
        {      
            if (a[i - 1] > a[i]) 
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0) break;  // 优化：提前终止
    }
}

答案：

• 最坏时间复杂度： $O(n^2)$（输入完全逆序时，需完整比较）。
• 最好时间复杂度：$O(n)$（输入已有序时，仅需一次遍历）。
• 平均时间复杂度：$O(n^2)$

---

指数阶O(2^n)

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

答案：

• 时间复杂度：$O(2^N)$
• 原因：递归树呈指数增长，每层调用次数约为 $2^N$

总结

-----------------------------------------

常见空间复杂度计算举例

常数阶O(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)$
• 原因：仅使用了常数个额外变量（end、exchange、i），与输入规模 $n$ 无关。
• 关键点：冒泡排序是原地排序算法，不依赖额外存储空间。

线性阶O(n)

//Fibonacci的空间复杂度
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;
}

答案：

• 空间复杂度：$O(n)$
• 原因：动态分配了大小为 $n+1$ 的数组 fibArray，空间占用与输入规模 $n$ 成正比。

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

答案：

• 空间复杂度：$O(n)$
• 原因：递归深度为 $N$，每次递归调用会在调用栈中保存一帧（包括：返回地址、局部变量等），共占用 $O(n)$ 的栈空间。

总结：

-----------------------------------------

复杂度的oj练习

面试题 17.04. 消失的数字

题目介绍

方法一：

class Solution 
{
public:
    int missingNumber(vector<int>& nums) 
    {
        //第一种思路：
        //1.先将数字0~n的和求出来
        //2.接着将这个和减去数组nums中的每一个元素
        //这样最终得到的结果就是消失的数字
        
        //1.
        int n=nums.size();
        int sum=(0+n)*(n+1)/2;
        //2.
        for(auto it:nums)
        {
            sum-=it;
        }

        return sum;
    }
};

方法二：

class Solution 
{
public:
    int missingNumber(vector<int>& nums) 
    {
        // 第二种思路：
        // 1.将数组中的所有的元素都于值为0的x进行异或
        // 2.再将这个值和0~n的每个值进行异或
        //最终x的值就是消失的数字

        //1.
        int x = 0;
        for (auto it : nums) 
        {
            x ^= it;
        }

        // 2.
        for (int i = 0; i <= nums.size(); i++) 
        {
            x ^= i;
        }
        return x;
    }
};

异或运算（XOR）有几个重要特性：

1. 任何数和自身异或结果为0：a ^ a = 0
2. 任何数和0异或结果为它本身：a ^ 0 = a
3. 异或运算满足交换律和结合律

算法思路：

1. 假设完整的数字序列是 0, 1, 2, ..., n，共 n+1 个数字
2. 给定的数组 nums 包含这 n+1 个数字中的 n 个（缺少一个）
3. 如果我们把所有数字（包括缺失的）都异或在一起，再异或上数组中的所有数字，结果就是缺失的数字

---

疑问：这个算法为什么是有效的？

假设数组是 [3,0,1]，缺失的数字是2：

1. 第一步异或数组元素：x = 3 ^ 0 ^ 1
2. 第二步异或完整序列：x = (3 ^ 0 ^ 1) ^ 0 ^ 1 ^ 2 ^ 3
3. 根据交换律重新排列：(0 ^ 0) ^ (1 ^ 1) ^ (3 ^ 3) ^ 2
4. 简化后：0 ^ 0 ^ 0 ^ 2 = 2

189. 轮转数组

题目介绍

方法一：

class Solution 
{
public:
    //实现：逆置数组元素的函数
    void reverse(vector<int>& nums,int l,int r)
    {
        //使用：遍历同一个数组中元素的对撞指针：
        for(int left=l,right=r;left<=right;left++)
        {
            int tmp=0;
            tmp=nums[left];
            nums[left]=nums[right];
            nums[right]=tmp;

            //更新right指针
            right--;
        }
    }
    void rotate(vector<int>& nums, int k) 
    {
        //思路：使用3段逆置：
        //1.前n-k个元素的逆置
        //2.后k个元素的逆置
        //3.整体的逆置
        
        int n=nums.size();
        k%=n;
        //1.
        reverse(nums,0,n-k-1);
        //2.
        reverse(nums,n-k,n-1);
        //3.
        reverse(nums,0,n-1);
        
    }
};

算法思想演示