当前位置：首页 > news >正文

数据结构与算法----顺序表和复杂度

news 来源：原创 2025/8/23 8:18:34

嘻嘻，我们用c语言来手撕顺序表！！！全程高能比喻+代码实战，保证你笑着学会！！！

引言

1、数据结构是计算机存储、组织数据的方式。算法是一系列计算步骤，用来将输入数据转化成输出结果。

2、耗费时间资源和空间（内存）资源。

3、衡量一个算法的好坏，从时间和空间俩个维度去衡量。

一、复杂度

时间复杂度讲解：

递归算法的时间复杂度=单次递归的时间复杂度*递归次数

1.定义

时间复杂度是啥？

官方黑话：描述算法运行时间随数据规模增长的趋势。
人话翻译：你的代码在数据量爆炸时，会“慢成狗”还是“稳如老狗” ？

核心思想：
- 不看具体执行时间（毕竟CPU不同）
- 只看增长趋势（数据量n→∞时，谁跑得更优雅）

2. 大O表示法：程序员的凡尔赛
用 O(...) 表示时间复杂度，只保留**“最影响速度的部分”：
- 忽略常数：O(2n) → O(n) （最高阶系数存在且不为1，去掉这个项目的常数系数）
- 忽略低次项：O(n² + 3n) → O(n²) ，只保留最高阶，因为当n不断变大，低阶对结果影响很小了
- 对数底数也忽略：O(log₂n) → O(logn)

举个栗子：
- 土豪算法：不管数据多少，时间固定 → O(1)（像直接开保险箱拿钱）
- 打工人算法：时间随数据量线性增长 → O(n)（像挨家挨户送快递）
-996算法：时间指数爆炸 → O(n²)（像全员开会，每两人都要握手）

3. 常见时间复杂度段位排行**

| 段位 | 代号 | 生活案例 | 代码案例 |
|--------------|-----------|-----------------------------------|-----------------------------------|
| 常数时间 | O(1) | 用钥匙开门 | 数组按索引访问 |
| 对数时间 | O(logn) | 翻字典查单词 | 二分查找 |
| 线性时间 | O(n) | 排队过安检 | 遍历数组 |
| 线性对数 | O(nlogn) | 全班同学各自翻字典 | 快速排序 |
| 平方时间 | O(n²) | 全员开会互相握手 | 冒泡排序 |
| 指数时间| O(2ⁿ) | 病毒式传播 | 穷举所有密码组合 |
| 阶乘时间 | O(n!) | 给n个人排座位的所有可能性

4、如何一眼看出时间复杂度？

（1）单层循环：---->O（n）

for(int i=0;i<n;i++)
{       //循环n次printf("打工第%d天\n",i);
}

数据量n多大，就循环多少次（线性增长）！！！

（2）双层嵌套循环---->O（n^2）

for(int i=0; i<n; i++) {       // 外层n次  for(int j=0; j<n; j++) {   // 内层n次  printf("社恐式握手：%d和%d\n", i, j);  }  
}

总操作数=n*n=n^2---->平方增长

（3）循环减半--->O（logn）

while(n > 0) {  printf("n=%d\n", n);  n = n / 2;   // 每次砍半  
}

解析：n经过多少次除以2会变成1？------>对数级（翻字典就是每次排除一半）

（4）递归分治----> O（nlogn）

void 归并排序(int arr[], int l, int r) {  if(l < r) {  int mid = (l+r)/2;  归并排序(arr, l, mid);      // 分治左半  归并排序(arr, mid+1, r);    // 分治右半  合并(arr, l, mid, r);       // O(n)的合并操作  }  
}

解析：（1）分治层数：O（logn）每次分俩半

（2）每层合并：O（n）（3）总时间：O（nlogn）---->优雅的排序

5、时间复杂度的灵魂拷问

Q1：O(n)一定比O(1)慢吗？
- 不一定！当n很小时，O(n)可能更快（比如n=5时，遍历5次比复杂计算快）
- 但n→∞时，O(1)永远碾压O(n)

Q2：O(2n)和O(n)有区别吗？
- 大O表示法认为没区别！只看趋势，常数系数忽略
- 但实际编码中，2n比n慢一倍（优化时要注意）

Q3：时间复杂度能100%反映实际速度吗？
- 不能！比如同样O(n)的算法，一个循环内做加法，另一个做除法，实际速度不同
- 时间复杂度是理论模型，实际速度还要看“常数项”和“硬件性能”

6、实战：顺序表操作时间复杂度分析

（1）随机访问元素

int getElement(SeqList* list, int index) {  return list->data[index];  // 直接算地址：base + index*sizeof(int)  
}

解析：时间复杂度O（1）（内存连续，一步到位）

（2）在位置i插入元素

void insert(SeqList* list, int i, int value) {  // 需要把i之后的元素全后移 → 移动次数 = size - i  for(int k=list->size; k>i; k--) {  list->data[k] = list->data[k-1];  }  list->data[i] = value;  
}

解析：时间复杂度：

（1）最好的情况是：插在末尾->O(1)(没人需要移动)

（2）最坏的情况是：插在开头->O（n）（全体后移，程序员落泪）

（3）平均情况：O（n）.

（3）删除位置i的元素

void delete(SeqList* list, int i) {  // 需要把i之后的元素全前移 → 移动次数 = size - i -1  for(int k=i; k<list->size-1; k++) {  list->data[k] = list->data[k+1];  }  
}

时间复杂度：和插入对称--->平均O（n）

7、总结归纳

【防秃指南】
1. 递归时间复杂度：用**递归树**或**主定理**分析（比如斐波那契数列O(2ⁿ)是灾难）
2. 均摊时间复杂度：像顺序表动态扩容，单次插入可能是O(n)，但均摊后是O(1)
3. 空间换时间：哈希表用O(n)空间换O(1)查询时间

---

【灵魂总结】
- O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)← 增长速度天梯图
- 优化方向：把高阶复杂度向低阶转化（比如用哈希表将查找从O(n)→O(1)）
- 核心思想：不要纠结具体时间，关注数据量增长时的趋势！

空间复杂度讲解：（因为算法需要，需要临时开辟空间）

空间复杂度计算的是变量的个数；函数运行时所需要的栈空间在编译时就已经确定好了，因此空间复杂度主要是通过函数在运行时候显式申请的额外空间来确定。

创建变量需要申请空间

【空间复杂度の灵魂拷问】
Q：空间复杂度是啥？能当饭吃吗？
A：它衡量算法**执行时占用内存随数据量增长的趋势**，不是具体内存值！
👉 举个栗子：
- **背包问题**：背包容量是O(n)，装的东西越多（数据量越大），空间需求越大
- **递归调用**：像俄罗斯套娃，每递归一次就压一层栈 → 空间复杂度可能爆炸！

举例：“代码的内存战场”

案例1、O（1）（极简主义）

int sum(int n) {  int result = 0;          // 只用了1个变量  for(int i=1; i<=n; i++) {  result += i;  }  return result;  
}

无论n多大，只有固定数量的变量--->内存用量不随n增长

案例2、O（n）空间（搬家式编程）

int* copyArray(int arr[], int n) {  int* newArr = (int*)malloc(n * sizeof(int)); // 申请n个int的空间  for(int i=0; i<n; i++) {  newArr[i] = arr[i];  }  return newArr;  
}

空间消耗与输入数据量n成正比---->数据翻倍，内存需求也翻倍！！！

案例3、O（n^2）空间（土豪式存储）

void createMatrix(int n) {  int** matrix = (int**)malloc(n * sizeof(int*));  for(int i=0; i<n; i++) {  matrix[i] = (int*)malloc(n * sizeof(int)); // 创建n×n的矩阵  }  
}

解析：总空间=n^2--->当n=1000时，占用约4MB（假设int是4字节），n=10000时400MB！

案例4、O（logn）空间（精致分层）

int binarySearchRecursive(int arr[], int left, int right, int target) {  if(left > right) return -1;  int mid = left + (right - left)/2;  if(arr[mid] == target) return mid;  else if(arr[mid] < target)   return binarySearchRecursive(arr, mid+1, right, target); // 递归右半  else  return binarySearchRecursive(arr, left, mid-1, target); // 递归左半  
}

解析：递归深度=log2 n---->每次递归压栈，但是栈空间随对数增长！！！

注意知识点：

1、递归的隐藏成本

int fibonacci(int n) {  if(n <= 1) return n;  return fibonacci(n-1) + fibonacci(n-2); // 空间复杂度O(n)？错！实际是O(n)的栈深度  }

实际空间复杂度是O（n），递归调用栈深度，但时间复杂度是O（2^n）,指数灾难

2、临时变量的陷阱

void func(int n) {  int temp[n]; // C99变长数组 → 空间复杂度O(n)！  // ...  }

虽然代码简洁，但可能引发栈溢出（大n时慎用）

3、空间复用技巧

// 优化前：O(n)空间  int* arr1 = malloc(n * sizeof(int));  int* arr2 = malloc(n * sizeof(int));  // 优化后：O(1)额外空间（原地操作）  for(int i=0; i<n; i++) {  arr1[i] = arr1[i] * 2; // 直接修改原数组  }

空间 vs 时间の哲学抉择】
- 空间换时间：哈希表用O(n)空间换取O(1)查询速度
- 时间换空间：某些压缩算法用计算时间换取更小存储空间
- 平衡之道：缓存策略（如LRU）在空间和时间之间找平衡

【灵魂总结】
1. 空间复杂度看的是算法运行过程中申请的额外空间（不包括输入数据本身）
2. 递归的空间复杂度 ≈ 递归深度 × 每次递归的空间消耗
3. 现代计算机内存充足，但处理海量数据时仍需警惕空间问题
4. 核心口诀：
- 能用O(1)别用O(n)
- 警惕递归的空间地雷
- 二维数组是空间吞噬兽

二、来自顺序表的自白

我，顺序表，c语言界的“动态数组plus”：

1、物理上连续：像军训队列每个元素必须贴贴站好

2、随机访问快：查元素像查寝室号，直接破门而入（O（1）时间复杂度）

3、增删慢如龟：中间插入/删除？全体元素军训式移动（O（n）时间复杂度）

三、代码的“解剖室”（动态顺序表的实现）

1、结构体定义（顺序表的“身份证”）

arr是指向动态数组的指针

typedef struct SeqList
{SLDataType* arr;int size;//有效数据个数int capacity;//空间容量
}SL;

2、初始化顺序表（申请地盘）

void SLInit(SL* ps)//形参  形参是实参值的拷贝
{ps->arr = NULL;//对指针通过箭头的方式来解引用->ps->size = ps->capacity = 0;}

定义动态顺序表的结构：

//定义动态数据表的结构
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;//有效数据个数int capacity;//空间容量
}SL;
//typedef struct SeqList SL;这俩种都可以

判断空间是否足够：

void SLCheckCapacity(SL* ps)
{
//判断空间是否足够if (ps->size==ps->capacity)//有效数据个数和空间容量{//增容,增容一般是成倍数增容，3倍、2倍....假如每次只增加一个空间\会出现频繁增容，重新找空间int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//如果空间容量为0，就给4个空间\空间容量不为0，就扩大二倍！SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity*sizeof(SLDataType));//realloc的第二个参数单位是字节//因为capacity一开始初始化是0，所以要处理一下！！！if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;//内存分配成功后，arr指向新的内存分配空间,用完要freeps->capacity = newCapacity;}
}

2、顺序表头删

void SLPopFront(SL* ps)
{assert(ps&&ps->size);//参数不能为NULL，顺序表也不为NULLfor (int i = 0;i < ps->size-1;i++)//  注意：i<ps->size -1，需要一会画图来描述！！！！！！！！！！{ps->arr[i] = ps->arr[i + 1];}ps->size--;//有效数字减小
}

3、顺序表头插

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size;i > 0;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;//插入一个数字，有效数字个数+1
}

4、顺序表尾插

void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//判断空间是否足够//空间足够时：ps->arr[ps->size] = x;++ps->size;
}

5、顺序表尾删

void SLPopBack(SL* ps)
{//ps限制的是参数不能直接给NULL//ps->size:顺序表为空，不能删。assert(ps && ps->size);//有效数字为0，是不可以尾删的,因为数组内没有数字ps->size--;}

6、顺序表的打印

void SLPrint(SL* ps)//打印顺序表
{assert(ps);for (int i = 0;i < ps->size;i++){printf("%d ", ps->arr[i]);}printf("\n");
}

7、顺序表在指定位置之前和之后插入数据

void SLInsert(SL* ps, int pos, SLDataType x)//指定位置之前插入数据，pos是对应的下标
{SLCheckCapacity(ps);assert(ps);assert(pos >= 0 && pos <= ps->size);//pos及之后的数据整体向后挪动一位for (int i = ps->size;i > pos;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;//在指定位置之后插入数据就是arr[pos+1]=x;ps->size++;  
}

8、顺序表删除指定位置数据

void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos;i < ps->size - 1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

9、顺序表查找元素的下标

//查找
int SLFind(SL* ps, SLDataType x)
{for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x){//找到了return i;}}//未找到return -1;
}

10、顺序表的销毁

//销毁
void SLDestroy(SL* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

引言