企业官网建设流程全解析

1. 算法效率

当我们评价一个算法的优劣时，通常会通过算法效率来评估。算法效率分为两部分：

• 时间效率：算法运行时耗费的时间
• 空间效率：算法运行过程中额外耗费的存储空间

但由于运行环境（电脑性能、编程语言、编译器优化）存在差异，同一份代码在不同机器上的实际耗时可能相差几十倍，直接测量并不可靠。因此我们通常采用事前分析估算的方法，由此引出时间复杂度和空间复杂度。

1.1 什么是时间复杂度

通俗地讲，时间复杂度就是：当输入数据量变大时，这段代码的运行时间增长得有多快。

它不关心「跑一次要几秒」，只关心「数据量翻倍时，时间涨几倍」。

常见从小到大排列：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

1.2 常见结构的基本复杂度

1.2.1 O(1)

与 n 无关的固定几条语句。

voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}intis_leap(intyear){return(year%4==0&&year%100!=0)||year%400==0;}

1.2.2 O(n)

单层循环

intfind_max(int*arr,intn){intmax_val=arr[0];// 1 次for(inti=0;i<n;i++)// n 次if(arr[i]>max_val)// 每次 1 次比较max_val=arr[i];// 偶尔 1 次returnmax_val;}

递归

intsum_to_n(intn){if(n==0)return0;returnn+sum_to_n(n-1);}

1.2.3 O(n²)

两层都跑满

for(inti=0;i<n;i++)for(intj=0;j<n;j++)count++;// n × n = n² 次

内层只跑一半

for(inti=0;i<n;i++)for(intj=i;j<n;j++)count++;// n + (n-1) + … + 1 = n(n+1)/2 次

1.2.4 O(log n)

每轮折半

intcount=0;intx=n;while(x>0){count++;x/=2;}

1.2.5 O(n log n)

外层 n 次 + 内层折半

for(inti=0;i<n;i++){// 外层 n 次intx=i;while(x>0){// 内层 log i 次count++;x/=2;}}

2. 什么是空间复杂度

和时间复杂度类似，空间复杂度也采用事前分析估算的方法，衡量的是当输入规模 n 增大时，算法额外占用的内存增长得有多快。

计算方法与时间复杂度基本一致，但有三条特有规则。

2.1 计算空间复杂度的三条前提

前提一：只算额外空间

默认不计入输入数据本身，只算算法为了完成计算而额外申请的空间，即辅助空间（auxiliary space）。

intfind_max(int*arr,intn){intmax_val=arr[0];// 唯一的额外变量for(inti=0;i<n;i++)if(arr[i]>max_val)max_val=arr[i];returnmax_val;}

输入arr占O(n)，但那是输入自带的。算法额外只用 1 个变量，故空间复杂度为O(1)。

前提二：看峰值，不看累计

voidrun(intn){int*a=malloc(n*sizeof(int));// 申请 n 个free(a);int*b=malloc(n*sizeof(int));// 再申请 n 个free(b);}

累计申请了2n个元素，但任何时刻最多只有 n 个同时存在，所以空间复杂度是O(n)，而不是O(2n)。

前提三：递归栈也要算

intfact(intn){if(n<=1)return1;returnn*fact(n-1);}

函数里只有一个参数，看似O(1)，实际是O(n)。因为每层递归都要把参数、返回地址、局部变量压入调用栈，n 层调用同时存在：
栈深度 = n，故空间复杂度为O(n)。

2.2 O(1)

只使用固定几个变量，称为原地（in-place）算法。

voidswap(int*a,int*b){intt=*a;*a=*b;*b=t;}voidreverse(int*arr,intn){inti=0,j=n-1;while(i<j){intt=arr[i];arr[i]=arr[j];arr[j]=t;i++;j--;}}

不论 n 是 10 还是 1000 万，额外内存始终是几个字节，故为O(1)。

冒泡、插入、选择、堆排序都是O(1)空间的原地排序，这是它们的重要优势。

2.3 O(n)

辅助数组

int*copy_array(int*src,intn){int*dst=malloc(n*sizeof(int));for(inti=0;i<n;i++)dst[i]=src[i];returndst;}

新数组包含 n 个元素，故为O(n)。

递归深度为 n

intsum_rec(intn){if(n==0)return0;returnn+sum_rec(n-1);}

这里的分析重点不是时间，而是空间：

• 时间：每层做一次加法，共 n 层 →O(n)
• 空间：n 层栈帧同时存在 →O(n)

注意：同一个函数可以有两个不同的复杂度。时间看「调用了多少次」，空间看「同时存在多少层」。这正是 1.2.2 与 2.4 使用相似代码的原因。

2.4 空间复杂度速查表

| 一维数组 n 个元素 |O(n)|
| 递归深度为 n |O(n)|

2.5 时间与空间的权衡

算法设计中，时间和空间往往不能同时最优，需要取舍，因此「用空间换时间」是工程中最常见的优化方向，因为内存通常比 CPU 时间便宜。

3. 小结

• 时间复杂度：数操作次数随 n 的增长趋势。顺序相加、嵌套相乘、分支取最大、递归写递推式，最后化简只留最高阶。
• 空间复杂度：数额外内存的峰值随 n 的增长趋势。只算额外空间，看峰值不看累计，递归要算栈深度。
• 两者都是事前估算，衡量的是增长趋势，而非具体耗时或占用。
• 判断依据是次数，不是循环层数；系数和常数不影响量级。