为什么数据结构与算法是程序员的“内功”
数据结构与算法是编程世界的基石。如果把编程比作建造房屋，那么：
编程语言是砖瓦水泥（工具）
数据结构是建筑结构（如何组织材料）
算法是施工方案（如何高效建造）
很多初级程序员会问：“我只是写业务逻辑，需要学算法吗？”
答案是：绝对需要。
理由很简单：
写出高性能代码：同样的功能，算法优劣决定程序是 0.1 秒完成还是 10 秒卡死
面试必考：大厂面试 80% 的时间都在考察数据结构与算法
解决问题的工具：遇到复杂问题，数据结构与算法是你最锋利的武器
代码质量的保障：理解底层原理才能写出健壮的代码
本文将从零开始，带你系统掌握初级程序员必须吃透的 7 大数据结构和 5 大算法思想，每一部分都有详细的原理讲解、代码实现和执行过程分析。
一、时间复杂度与空间复杂度：衡量算法的尺子
在学习具体的数据结构之前，我们必须先学会如何衡量一个算法的好坏。
1.1 什么是时间复杂度？
时间复杂度描述了算法执行时间随输入规模增长的变化趋势。它不关心具体运行时间（因为机器性能不同），而是关心操作次数的增长率。
https://fndvx.cn/
大O表示法：忽略常数项和低阶项，只保留最高阶项。
1.2 时间复杂度计算实战
// O(1) - 常数时间
// 无论输入多大，操作次数固定
function getFirstElement(arr) {
return arr[0]; // 只做一次操作
}
function isEven(num) {
return num % 2 === 0; // 一次取余，一次比较
}
// O(n) - 线性时间
// 操作次数与输入规模成正比
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) { // 循环 n-1 次
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 总操作次数 ≈ n，所以是 O(n)
// O(n²) - 平方时间
// 常见于双重循环
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) { // 外层循环 n 次
for (let j = 0; j < n - 1; j++) { // 内层循环 n 次
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
// 总操作次数 ≈ n × n = n²，所以是 O(n²)
// O(log n) - 对数时间
// 典型场景：二分查找
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // 抛弃左半部分
} else {
right = mid - 1; // 抛弃右半部分
}
}
return -1;
}
// 每次循环将搜索范围减半，操作次数 = log₂(n)
// 当 n=1,000,000 时，log₂(1e6) ≈ 20 次
// O(n log n) - 线性对数时间
// 典型场景：高效排序算法（归并排序、快速排序）
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
// 归并排序将数组不断二分（log n 层），每层需要合并 n 个元素
// 总复杂度：n × log n
1.3 常见复杂度对比
1.4 空间复杂度
空间复杂度描述算法额外消耗的存储空间随输入规模的变化趋势。
// O(1) - 常数空间
// 只使用固定数量的额外变量
function sum(arr) {
let total = 0; // 1 个变量
for (let i = 0; i < arr.length; i++) {
total += arr[i]; // 复用同一个变量
}
return total;
}
// 无论数组多大，只用了 total 和 i 两个变量
// O(n) - 线性空间
// 需要创建与输入规模成比例的额外空间
function duplicateArray(arr) {
const copy = new Array(arr.length); // 新数组长度 = n
for (let i = 0; i < arr.length; i++) {
copy[i] = arr[i];
}
return copy;
}
// 额外空间与输入数组大小成正比
// O(n²) - 平方空间
// 典型场景：创建二维矩阵
function createMatrix(n) {
const matrix = [];
for (let i = 0; i < n; i++) {
matrix[i] = new Array(n); // 每行有 n 个元素
for (let j = 0; j < n; j++) {
matrix[i][j] = 0;
}
}
return matrix;
}
// 总元素个数 = n × n = n²
1.5 复杂度分析技巧
// 技巧1：只看循环嵌套最深的部分
function example1(arr) {
let sum = 0; // O(1)
for (let i = 0; i < arr.length; i++) { // O(n)
sum += arr[i];
}
for (let i = 0; i < arr.length; i++) { // O(n)
for (let j = 0; j < arr.length; j++) { // O(n²)
console.log(i, j);
}
}
}
// 总体复杂度 = O(1) + O(n) + O(n²) = O(n²)（取最高阶）
// 技巧2：循环变量以乘法/除法增长的是对数级
function example2(n) {
let i = 1;
while (i < n) {
i = i * 2; // i 按倍数增长
}
}
// 复杂度 = O(log n)
// 技巧3：递归算法可以用递归树分析
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
// 复杂度 = O(2ⁿ)（指数爆炸）
