企业官网建设流程全解析

一文吃透数据结构与算法基础 | 复杂度分析核心详解

前言

不管是校招面试、后端开发、前端业务优化还是算法刷题，数据结构与算法都是程序员必备底层基本功。
很多新手一上来就死磕链表、二叉树、各种排序，却跳过基础概念与复杂度分析，写出低效代码，面试被问复杂度直接卡壳。

本文基于核心课堂笔记扩充优化，搭配分类图示标记、代码示例、化简规则，完整梳理数据结构、算法、时空复杂度全套入门理论，适合零基础自学、期末复习、面试速看。

一、数据结构核心基础概念

1. 五大基础术语（层级关系）

1. 数据
   所有能输入计算机、可被处理的符号总称：数字、文本、图片、音频、视频都属于数据。
2. 数据元素
   数据的基本操作单位，是数据对象里的独立个体。
   例：学生信息表中的一整条学生记录。
3. 数据项
   数据最小拆分单位，无法再细分，组成数据元素。
   例：学生记录里的学号、姓名、年龄、班级。
4. 数据对象
   性质相同的数据元素的集合，是数据的子集。
   例：全校所有学生、1~100 全部整数。
5. 数据结构
   相互存在特定关系的数据元素的集合，分为两大维度：

• 逻辑结构：数据元素之间抽象关系
• 物理结构：数据在内存真实存储形式

2. 逻辑结构（4大类）

仅描述元素抽象关系，和内存存放无关。

3. 物理存储结构（2大类）

逻辑结构需要物理载体落地，决定内存布局。

① 顺序存储结构

内存地址连续整块存放元素。

[10][20][30][40] 连续地址

• 优点：支持下标随机访问，查询速度快。
• 缺点：插入/删除需要移动大量元素，扩容成本高。
• 代表：数组int arr[100];。

② 链式存储结构

数据分散在零散内存中，依靠指针保存下一个节点的地址

[10 | *next] → [20 | *next] → [30 | null]

• 优点：插入、删除仅修改指针，无需移动元素
• 缺点：不支持随机访问，遍历需要逐个跳转
• 代表：单链表、双向链表

二、算法完整认知

1. 数据结构与算法关系

数据结构 = 数据怎么存
算法 = 数据怎么操作
二者不可分割：合适的数据结构能极大优化算法效率。

经典对比案例：求 1~100 累加和

方式 1：循环遍历（暴力算法）

intsum=0;for(inti=1;i<=100;i++){sum+=i;}

执行次数：100 次，依赖数据规模

方式 2：高斯等差数列公式（数学优化算法）

intsum=(1+100)*100/2;

执行次数：固定 3 次，和数据规模无关
两种方案实现同一需求，但执行效率差距巨大，这就是复杂度分析的意义。

2. 算法定义

算法是解决特定问题求解步骤的有限指令序列，每条指令对应一个或多个计算机操作。

重点：不存在通用算法能解决所有问题，不同业务场景需要针对性设计算法。

3. 算法五大硬性特性（缺一不可）

1. 输入：0 个或多个输入数据
2. 输出：至少 1 个输出，算法必须产出结果
3. 有穷性：有限步骤内自动结束，无无限死循环，执行时长可控
4. 确定性：每一步含义唯一、无歧义；相同输入一定得到相同输出
5. 可行性：每一步操作都能通过有限次运算完成，不存在无法执行的步骤

4. 优质算法四大设计标准

1. 正确性：合法输入、边界值、极值都能输出正确结果
2. 可读性：逻辑清晰、注释规范，拒绝晦涩炫技代码，方便团队维护
3. 健壮性：兼容非法输入（空值、负数、越界参数），不会直接程序崩溃
4. 时间效率高 + 存储占用低：运行速度快，额外内存开销小

三、时间复杂度：衡量算法运行快慢

1. 核心原理

时间复杂度 ≠ 程序真实运行毫秒数
用于描述执行次数随数据规模 N 增长的变化趋势
计算公式：
程序总执行时间=单条指令耗时×指令总执行次数程序总执行时间 = 单条指令耗时 × 指令总执行次数程序总执行时间=单条指令耗时×指令总执行次数
硬件单条指令耗时固定，因此只需要统计循环、操作执行次数。

2. 大 O 渐进表示法化简三大规则

统一简化复杂度函数T(N)T(N)T(N)，只关注增长趋势：

1. 只保留最高阶项，丢弃全部低阶项
2. 最高阶项系数不为 1 时，直接去掉系数
3. 表达式无 N 相关项，统一用常数O(1)O(1)O(1)代替

代码示例化简演示

示例 1：T(N)=3N2+5N+20T(N) = 3N^2 + 5N + 20T(N)=3N2+5N+20

• 最高阶N2N^2N2，去掉系数3 →O(N2)O(N^2)O(N2)

// 两层嵌套循环，复杂度 O(N²)for(inti=0;i<n;i++){for(intj=0;j<n;j++){// 单次操作}}

示例 2：T(N)=1000T(N) = 1000T(N)=1000

• 无N项 →O(1)O(1)O(1)

// 固定次数执行，和n无关inta=10;intb=20;intc=a+b;

示例 3：T(N)=4N+100T(N) = 4N + 100T(N)=4N+100

• 最高阶N，去掉系数4 →O(N)O(N)O(N)

// 单层循环，复杂度 O(N)for(inti=0;i<n;i++){}

常见复杂度排序（由快到慢）

O(1)<O(log⁡N)<O(N)<O(Nlog⁡N)<O(N2)<O(2N)O(1) < O(\log N) < O(N) < O(N \log N) < O(N^2) < O(2^N)O(1)<O(logN)<O(N)<O(NlogN)<O(N2)<O(2N)

四、空间复杂度：衡量算法内存开销

1. 核心概念

空间复杂度统计算法运行时额外动态开辟的临时空间，不包含原始输入数据占用的内存，同样使用大 O 表示法。
统计对象：临时变量、动态数组、链表、递归额外栈等。

重要注意点

函数默认调用栈空间在编译阶段已确定，不计入空间复杂度；仅统计运行时手动显式申请的额外内存。

代码示例

示例 1：常数空间 O(1)

仅定义固定数量临时变量，无动态内存。

intfunc(intn){inta=1;intb=2;returna+b;}

示例 2：线性空间 O(N)

根据输入规模 n 动态创建数组，额外空间随 N 变化

intfunc(intn){// 动态开辟长度n的数组int*arr=(int*)malloc(sizeof(int)*n);returnarr[0];}

五、核心知识点总结

1. 数据结构分为逻辑关系和物理存储两层，4 类逻辑、2 种存储是底层根基；
2. 算法有 5 条硬性约束，工业开发中优先保证正确性、可读性，再优化时空效率；
3. 时间复杂度只关心操作次数增长趋势，不看真实运行时间；
4. 空间复杂度只统计运行时手动开辟的额外内存，固定栈空间不参与计算；
5. 大 O 渐进表示法是行业统一标准，忽略常数、低阶项，只保留最高阶增长趋势。

结尾

掌握这套底层理论后，再学习链表、树、排序、查找等具体结构与算法，才能精准判断不同写法的性能优劣，写出高效、规范的工程代码，同时轻松应对面试复杂度分析提问。