算法复杂度分析：时间与空间的量化评估
一、复杂度的核心概念
在算法设计中，效率评估主要分为两个维度：运行速度（时间复杂度）和内存占用（空间复杂度）。前者衡量算法执行所需时间随输入规模增长的趋势，后者则关注算法运行期间临时存储空间的增长规律。两者均采用大O渐进表示法进行抽象表达。
二、时间复杂度的推导方法
实际分析时无需精确计数，只需关注主导项。推导步骤如下：
- 忽略常数项（如加法中的固定值）
- 保留最高阶项
- 若最高阶存在且系数不为1，则去除该系数
示例1：双重循环嵌套
void func(int n, int m) {
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
++count;
}
}
for (int k = 0; k < 2 * n; ++k) {
++count;
}
while (m--) {
++count;
}
}总操作次数为：n×m + 2n + m。当n和m趋于无穷时，主导项为n×m，因此时间复杂度为O(n×m)。
示例2：独立循环组合
void func2(int a, int b) {
int sum = 0;
for (int i = 0; i < a; ++i) ++sum;
for (int j = 0; j < b; ++j) ++sum;
}由于两循环独立且变量未知，时间复杂度为O(a + b)。若已知关系可进一步简化。
示例3：常量操作
void func3() {
int val = 0;
for (int i = 0; i < 50; ++i) ++val;
}无论循环多少次，只要次数恒定，时间复杂度均为O(1)。
示例4：线性搜索
const char* find_char(const char* str, char target) {
while (*str != '\0') {
if (*str == target) return str;
++str;
}
return nullptr;
}最坏情况下需遍历整个字符串，长度为N，故时间复杂度为O(N)。通常以最坏情况为准。
示例5：冒泡排序
void bubble_sort(int* arr, size_t len) {
for (size_t end = len; end > 0; --end) {
int flag = 0;
for (size_t i = 1; i < end; ++i) {
if (arr[i-1] > arr[i]) {
swap(&arr[i-1], &arr[i]);
flag = 1;
}
}
if (!flag) break;
}
}外层循环共执行约n/2 × (n+1)次，主导项为n²，因此时间复杂度为O(n²)。
示例6：二分查找
int binary_search(int* arr, size_t len, int key) {
int left = 0, right = len;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (arr[mid] < key) left = mid + 1;
else if (arr[mid] > key) right = mid;
else return mid;
}
return -1;
}每次将搜索范围减半，最多需log₂n次比较，时间复杂度为O(log n)。
示例7：递归阶乘
long long factorial(size_t n) {
return n <= 1 ? n : factorial(n - 1) * n;
}递归深度为n，每层调用使用常数空间，整体空间复杂度为O(n)，时间复杂度也为O(n)。
三、空间复杂度的判定原则
空间复杂度衡量的是算法运行过程中所使用的额外存储空间的最大值，不包括输入本身。
示例1：原地排序
void sort_inplace(int* data, size_t size) {
for (size_t i = 1; i < size; ++i) {
int temp = data[i];
size_t j = i;
while (j > 0 && data[j-1] > temp) {
data[j] = data[j-1];
--j;
}
data[j] = temp;
}
}仅使用了几个局部变量，空间复杂度为O(1)。
示例2：动态数组生成斐波那契序列
long long* generate_fib(size_t n) {
if (n == 0) return nullptr;
long long* result = (long long*)malloc((n + 1) * sizeof(long long));
result[0] = 0; result[1] = 1;
for (int i = 2; i <= n; ++i) {
result[i] = result[i-1] + result[i-2];
}
return result;
}动态分配了n+1个元素的空间，空间复杂度为O(n)。
示例3：递归实现阶乘
long long fact_recursive(size_t n) {
return n <= 1 ? n : fact_recursive(n - 1) * n;
}递归调用栈深度为n，每层占用常数空间，因此空间复杂度为O(n)。
