时间与空间复杂度的深入解析
在算法分析中，评估代码效率的核心指标包括时间复杂度和空间复杂度。我们通过具体示例来理解其计算逻辑。
首先分析以下线性累加函数：
int calculate(int n) {
int total = 0;
int index = 1;
for (; index <= n; ++index) {
total += index;
}
return total;
}
该函数中，total += index 是执行频率最高的语句，共执行 n 次。其他初始化操作均为常数级。因此整体时间复杂度为 O(n)。
接下来观察嵌套循环的情况：
int compute(int n) {
int result = 0;
int outer = 1;
int inner = 1;
for (; outer <= n; ++outer) {
inner = 1;
for (; inner <= n; ++inner) {
result += outer * inner;
}
}
return result;
}
外层循环执行 n 次，内层循环也执行 n 次，总操作次数为 n × n = n²。因此时间复杂度为 O(n²)。
由此可归纳出三大基本法则：
- 加法原则：若代码分段执行，总复杂度取各部分最大量级。例如，O(n) + O(n²) = O(n²)
- 乘法原则：嵌套结构的复杂度为内外层复杂度的乘积。如两层循环各为 O(n)，则整体为 O(n²)
- 主项忽略原则：高阶项主导复杂度表现，低阶项与常数可忽略。例如，O(3 + 2n + 5n²) 简化为 O(n²)
再来看对数阶循环：
int fastLoop(int n) {
int value = 1;
while (value <= n) {
value *= 2;
}
return 0;
}
每次 value 翻倍，从 1 开始，直到超过 n。其迭代次数满足 2^k ≥ n，解得 k = log₂n。故时间复杂度为 O(log n)。
同理，若每次乘以 3，则迭代次数为 log₃n。由于不同底数的对数之间仅差一个常数因子（如 log₃n = log₃2 × log₂n），而大 O 表示法中常数系数被忽略，因此所有对数阶统一记作 O(log n)。
关于空间复杂度，关注的是运行过程中动态分配的内存大小。
void displaySequence(int n) {
int counter = 0;
int* array = new int[n];
for (counter = 0; counter < n; ++counter) {
array[counter] = counter * counter;
}
for (counter = n - 1; counter >= 0; --counter) {
print(array[counter]);
}
}
其中，int counter 占用固定空间，属于常数阶；array 分配了 n 个整型元素，占用线性空间。其余操作未引入额外存储。因此空间复杂度为 O(n)。
常见空间复杂度类型包括：
- O(1)：仅使用固定数量变量
- O(n)：动态分配一维数组
- O(n²)：二维数组或双重嵌套结构
- O(log n)、O(n log n)：虽存在但较少见于基础场景
综上，时间复杂度聚焦于"执行次数的增长趋势"，空间复杂度衡量"内存使用的规模增长"。二者均采用大 O 记号进行抽象表达，忽略常数与低阶项，突出核心增长规律。
