时间和空间复杂程度计算规则

时间复杂度和空间复杂度的计算是算法分析的重要部分。以下是详细的计算方法、示例，以及需要注意的要点。

---

1. 时间复杂度

时间复杂度描述算法执行所需时间随输入规模增长的增长关系，通常用 大 $O$ 表示法 来表示，关注输入规模 $n$ 的增长率。

---

1.1 时间复杂度的计算方法

1. 找到最内层操作：

   • 确定算法中执行次数最多的基本操作（如赋值、比较、加法等）。

2. 统计执行次数：

   • 从外到内，计算循环、递归或逻辑分支中基本操作的执行次数。

3. 保留最高阶：

   • 只保留执行次数随输入规模 $n$ 增长最快的部分，忽略低次项和常数系数。

---

1.2 常见时间复杂度

1. 常数时间：$O(1)$

   • 不依赖于输入规模，执行次数恒定。

   int a = 10;
   a = a + 1; // 常数时间
   

2. 线性时间：$O(n)$

   • 基本操作执行次数与输入规模 $n$成正比。

   for (int i = 0; i < n; i++) {
       printf("%d\n", i); // 执行 n 次
   }
   

3. 平方时间：$O(n^2)$

   • 嵌套循环中，每个循环迭代 $n$次，基本操作执行 $n^2$次。

   for (int i = 0; i < n; i++) {
       for (int j = 0; j < n; j++) {
           printf("%d, %d\n", i, j); // 执行 n * n 次
       }
   }
   

4. 对数时间：$O(\log n)$

   • 规模每次减小一半，通常出现在二分查找等算法中。

   while (low <= high) {
       mid = (low + high) / 2;
       if (arr[mid] == target)
           return mid;
       else if (arr[mid] < target)
           low = mid + 1;
       else
           high = mid - 1;
   }
   

5. 线性对数时间：$O(n\log n)$

   • 通常出现在分治算法（如归并排序）。

   void mergeSort(int arr[], int n) {
       if (n <= 1) return;
       int mid = n / 2;
       mergeSort(left, mid);
       mergeSort(right, n - mid);
       merge(left, right, arr); // 合并操作执行 O(n)
   }
   

6. 指数时间：$O(2^n)$

   • 通常出现在递归枚举（如穷举法）。

   void subset(int[] arr, int n) {
       if (n == 0) return;
       subset(arr, n - 1);
       subset(arr + [arr[n]], n - 1); // 分成两种选择
   }
   

---

1.3 示例：时间复杂度的具体分析

示例 1：

for (int i = 0; i < n; i++) {
    printf("%d\n", i);
}

• 基本操作：printf。
• 执行次数：$n$。
• 时间复杂度：$O(n)$。

示例 2：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("%d, %d\n", i, j);
    }
}

• 基本操作：printf。
• 执行次数：外层循环执行 $n$次，内层循环每次执行$n$次，总共 $n\times n=n^2$ 次。
• 时间复杂度：$O(n^2)$。

示例 3：

int i = 1;
while (i <= n) {
    i *= 2;
}

• 基本操作：i *= 2。
• 执行次数：每次迭代 $i$乘 2，最多执行 $lo{g}_{2}n$ 次。
• 时间复杂度：$O(\log n)$。

---

2. 空间复杂度

空间复杂度描述算法运行时使用的额外内存随输入规模增长的关系，也用 大 O 表示法 表示。

---

2.1 空间复杂度的计算方法

1. 统计额外变量：

   • 计算算法使用的变量、数组、递归栈的大小。

2. 输入空间不计入：

   • 输入数组或数据结构的存储空间不属于额外空间。

3. 递归调用的栈空间：

   • 如果算法有递归，递归栈的深度乘以每层所需空间。

---

2.2 常见空间复杂度

1. 常数空间：$O(1)$

   • 使用固定数量的变量，无论输入规模如何。

   int a = 0;
   a++;
   

2. 线性空间：$O(n)$

   • 使用额外的数组或数据结构，大小与输入规模 $n$成正比。

   int* temp = (int*)malloc(n * sizeof(int));
   

3. 递归栈空间：$O(n)$

   • 深度为 $n$的递归会使用 $O(n)$ 的栈空间。

   void recursive(int n) {
       if (n == 0) return;
       recursive(n - 1);
   }
   

---

2.3 示例：空间复杂度的具体分析

示例 1：

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += i;
}

• 使用的额外变量：sum 和 i，总共占用固定空间。
• 空间复杂度：$O(1)$。

示例 2：

int* temp = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
    temp[i] = i;
}

• 使用的额外空间：长度为 $n$的数组 temp。
• 空间复杂度：$O(n)$。

示例 3：

void recursive(int n) {
    if (n == 0) return;
    recursive(n - 1);
}

• 每次递归调用都会占用一个栈帧。
• 如果递归深度为 $n$，栈空间总大小为 $O(n)$。

---

3. 时间复杂度和空间复杂度的对比

算法类型	时间复杂度	空间复杂度
直接循环	$O(n)$	$O(1)$
嵌套循环	$O(n^2)$	$O(1)$
递归算法	$O(2^n)$	$O(n)$
分治算法	$O(n\log n)$	$O(n)$
动态规划	$O(n^2)$	$O(n^2)$

---

总结

• 时间复杂度：
  • 根据基本操作的执行次数，分析循环、分支、递归的增长趋势。
• 空间复杂度：
  • 根据额外变量、数组、递归栈的大小，估算内存使用的增长关系。

理解和计算复杂度需要结合实际代码逐行分析，尤其要关注循环和递归结构的执行规律。

原文地址：https://blog.csdn.net/zzx2016zzx/article/details/143888190

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！