时间复杂度和空间复杂度 part2

一，空间复杂度

空间复杂度是衡量一个算法在执行过程中所需内存空间的量度。它反映了算法随着输入数据规模（通常是 nn）的增加，所消耗的内存量如何变化。空间复杂度是分析算法效率的一个重要方面，尤其是在内存资源有限的环境中，如嵌入式系统、移动设备等。

空间复杂度的定义

空间复杂度指的是算法在执行过程中所使用的额外空间，包括以下几类空间：

1. 输入数据空间：这是存储输入数据所占的空间，通常在空间复杂度的计算中不考虑，假设输入数据已经提供。
2. 辅助空间：即算法在执行过程中需要额外申请的空间（除了输入数据外），包括：
   • 临时变量
   • 数据结构（如数组、栈、队列等）
   • 递归调用栈空间

常见的空间复杂度

空间复杂度通常以大 O 表示法来表示，和时间复杂度一样，用来描述算法所需要的内存空间随着输入数据规模的变化趋势。以下是一些常见的空间复杂度：

1. O(1)：常数空间复杂度，表示算法只使用固定的内存量，与输入数据的大小无关。举个例子，简单的数值计算、交换两个数等操作通常是 O(1) 空间复杂度。

2. O(n)：线性空间复杂度，表示算法的空间需求与输入数据的大小成线性关系。例如，复制一个数组或创建一个与输入数据大小相同的辅助数据结构（如数组或链表），通常需要 O(n) 的空间。

3. O(n²)：平方空间复杂度，表示算法的空间需求与输入数据的平方成正比。例如，某些矩阵操作（如二维数组的存储）可能需要 O(n²) 的空间。

4. O(log n)：对数空间复杂度，表示算法的空间需求与输入数据的对数成正比。例如，递归算法中，如果递归的深度为对数级别，那么它的空间复杂度通常为 O(log n)。

空间复杂度的影响因素

空间复杂度不仅仅取决于输入数据的大小，还与算法内部使用的数据结构、存储方式、递归的深度等因素有关。以下是影响空间复杂度的一些因素：

1. 数据结构的使用：不同的数据结构占用的内存空间不同。例如，使用链表存储数据通常比数组占用更多的空间，因为链表需要额外存储指针，而数组只存储数据。
2. 递归深度：递归算法会占用栈空间，递归的深度越大，空间复杂度也越大。例如，递归树的深度与输入数据的规模相关时，可能会导致 O(n) 或 O(log n) 的空间复杂度。
3. 辅助数据存储：一些算法需要临时存储中间结果，这也会影响空间复杂度。例如，归并排序需要额外的数组来存储合并的中间结果，空间复杂度是 O(n)。

空间复杂度的计算方法

计算空间复杂度时，我们通常关心算法在执行过程中使用的额外空间，而不是输入数据所占用的空间。以下是几种常见的空间使用情形：

• 常数空间（O(1)）：如果算法使用的空间数量不依赖于输入数据的大小。例如，算法只使用几个临时变量来进行计算。

  示例：

  def sum_array(arr): total = 0 # 常数空间

• for num in arr: total += num return total

• 线性空间（O(n)）：如果算法使用的数据结构的大小随着输入数据规模的增大而增大。例如，创建一个新的数组来存储输入数据的副本。

  示例：

  def copy_array(arr): new_arr = arr[:] # 新数组，空间复杂度为O(n) return new_arr

• 递归空间（O(n) 或 O(log n)）：递归算法通常会占用栈空间，递归深度越大，空间复杂度越大。例如，深度为 n 的递归算法会消耗 O(n) 空间，而深度为 log n 的递归算法会消耗 O(log n) 空间。

  示例：

  def factorial(n): if n == 1: return 1 return n * factorial(n - 1) # 空间复杂度是O(n)，因为递归深度为n

总结

空间复杂度是衡量算法执行过程中所需内存空间的量度。它关注的是算法在执行期间占用的额外内存（除了输入数据所占空间外）。对于任何一个算法，我们都应该关注其空间复杂度，尤其是在内存资源有限的环境中。常见的空间复杂度包括 O(1)、O(n)、O(n²) 等，不同的算法和数据结构会导致不同的空间复杂度，设计高效的算法时，需要权衡时间和空间的消耗。

动态扩容

动态数组的扩容是动态数据结构（如 ArrayList、Vector 等）在其容量不足时自动增加空间以容纳更多元素的过程。与静态数组不同，动态数组的大小不是固定的，而是可以根据需要动态调整。在实际操作中，动态数组的扩容过程通常是通过重新分配更大的内存空间并将旧数据复制到新位置来实现的。

动态数组的基本操作

动态数组的核心特性是能够在不预先知道元素数量的情况下，动态调整数组的大小。大多数情况下，动态数组支持以下操作：

• 插入元素：动态数组可以随时向其尾部添加元素。
• 查找元素：可以根据索引快速访问数组中的元素。
• 删除元素：可以删除特定元素，虽然删除操作通常会涉及元素的位移。
• 扩容：当数组的大小不够时，动态数组会自动扩展其存储空间。

扩容的原理

动态数组扩容的目的是为了解决数组在插入新元素时可能遇到的容量不足问题。通常情况下，扩容是通过以下步骤实现的：

1. 判断是否需要扩容：当动态数组的当前容量已满且再插入元素时，需要扩容。此时，通常会将数组的容量增加到原来的 2倍（或者有时是固定增量），以保持较高的空间利用率和操作效率。

2. 重新分配内存：扩容时，动态数组会分配一个新的、更大的内存块，通常是原数组大小的两倍。

3. 复制数据：将原数组中的所有元素复制到新的、更大的内存块中。

4. 更新指针/引用：将新的数组指针（或者引用）赋给动态数组变量，原数组的内存空间就可以被垃圾回收（在一些语言中，如Java和Python）。

扩容的性能分析

1. 扩容时的时间复杂度：

   • 扩容操作本身需要 O(n) 时间，因为它涉及到将数组中的每个元素复制到新的内存空间。
   • 但值得注意的是，扩容并不会在每次插入时都发生，而是周期性地发生。具体来说，扩容通常是每次数组容量不足时，扩容到原来的 2 倍，因此在进行 n 次插入时，扩容操作平均需要的时间为 O(1)（摊销时间复杂度）。

   摊销分析：假设每次扩容操作都是将数组的大小翻倍，那么对于 n 次插入，扩容操作的总成本是：

   • 第一次扩容将数组大小从 1 扩展到 2（复制 1 个元素）
   • 第二次扩容将数组大小从 2 扩展到 4（复制 2 个元素）
   • 第三次扩容将数组大小从 4 扩展到 8（复制 4 个元素）
   • ...
   • 最后一轮扩容将数组大小从 2^k 扩展到 2^(k+1)（复制 2^k 个元素）

   因此，整个扩容操作的总成本是 1 + 2 + 4 + 8 + ... + n，这可以简化为 O(n)。当将这个总成本摊销到 n 次插入操作中时，平均每次插入的扩容时间复杂度为 O(1)。

2. 空间复杂度：

   • 动态数组的空间复杂度为 O(n)，其中 n 是数组当前存储的元素个数。因为动态数组需要存储实际的元素以及动态扩容后的额外空间（通常会分配多余空间以提高效率），所以其空间复杂度是与元素个数成线性关系的。
   • 如果扩容的策略是每次翻倍，可能会导致在某一时刻，数组的实际元素数小于数组的总容量，造成一定的空间浪费，但这种浪费通常是有限的。

何时扩容：容量和负载因子

扩容的时机和策略通常依赖于负载因子（load factor）。负载因子是指数组中已使用空间与数组总容量的比例，常见的负载因子约定为 0.75。这意味着，当数组的元素数量达到当前容量的 75% 时，就会触发扩容操作。

• 例如，如果动态数组当前的容量是 10，当其中的元素数量达到 7 时，负载因子达到 0.75，这时就会触发扩容，将容量增大为原来的 2 倍，变为 20。

均摊时间复杂度

 
**均摊时间复杂度**（Amortized Time Complexity）是对一系列操作在最坏情况下的平均时间复杂度的分析方法。它用于描述在一系列操作中，某个操作的平均成本，而不仅仅是单个操作的最坏情况。均摊分析通常应用于那些**偶尔有昂贵操作**（如扩容）但大多数操作是便宜的算法或数据结构。

### 1. **什么是均摊时间复杂度**

均摊时间复杂度是指通过将多个操作的总时间复杂度平均到每一个操作上，从而得出操作的平均成本。它帮助我们理解在长期内进行大量操作时，每个操作的“平均”成本，而不仅仅是单个操作的最坏情况。

举个例子，在 **动态数组扩容** 这样的场景中，扩容本身可能是一个昂贵的操作（O(n)），但是在多个操作中，如果扩容是偶尔发生的，它的影响会被“摊销”到其他便宜的操作上，使得每个操作的均摊复杂度变得更低。

### 2. **均摊时间复杂度的例子：动态数组扩容**

动态数组（如 `ArrayList` 或 `Vector`）的扩容机制通常会导致偶尔发生昂贵的操作——即当数组满时，必须将数据复制到更大的内存中。这种扩容操作的时间复杂度为 **O(n)**，但是这种情况并不是每次插入操作都会发生的。

假设动态数组的容量为 `n`，当它达到 `n` 个元素时，插入第 `n+1` 个元素会触发扩容。扩容操作将数组大小翻倍，并将所有 `n` 个元素复制到新数组中。

如果我们对 `n` 次插入操作进行分析，第一次扩容操作的时间复杂度是 **O(n)**，第二次扩容时的时间复杂度是 **O(2n)**，依此类推。看起来这很昂贵，但实际上，扩容操作并不会每次都发生，因此可以通过**摊销**计算均摊时间复杂度。

### 3. **均摊时间复杂度的计算**

考虑一个有 `n` 次插入操作的动态数组，扩容的发生规律是容量每次翻倍。虽然扩容的时间复杂度为 **O(n)**，但因为它是每次容量达到当前容量的上限时才发生一次，并且扩容的次数相对较少，所以我们可以用均摊时间复杂度来计算。

假设我们插入 `n` 个元素：

- **第一次扩容**：当插入第一个元素时，不需要扩容。当插入第 `n+1` 个元素时，需要扩容，复制 `n` 个元素到新的数组，时间复杂度为 **O(n)**。
- **第二次扩容**：当数组容量达到 `2n` 时，插入第 `2n+1` 个元素时，需要扩容，复制 `2n` 个元素，时间复杂度为 **O(2n)**。
- **以此类推**，每次扩容的时间复杂度为原来的一倍。

总的时间复杂度是：

$$
O(1) + O(1) + \cdots + O(1) + O(n) + O(2n) + O(4n) + \cdots
$$

这个和是一个几何级数，摊销下来，整个插入操作的总时间复杂度为 **O(n)**，而均摊到每次插入，时间复杂度为 **O(1)**。

### 4. **为什么要使用均摊分析**

- **反映真实性能**：均摊分析能够更准确地反映实际操作的性能，特别是对于那些偶尔需要昂贵操作的数据结构。例如，动态数组虽然扩容是昂贵的，但在插入大量元素时，大多数插入操作的时间复杂度是常数级别的 **O(1)**。
- **避免过度优化**：最坏情况分析往往很保守，无法准确描述实际的性能。在实际应用中，大多数操作都是常数时间复杂度的，如果过度关注最坏情况复杂度，可能会导致对性能的误判，均摊时间复杂度则能够提供更实际的视角。
- **分析复杂数据结构**：对于某些数据结构，如 `splay tree`、`hash table` 等，均摊分析能够有效计算实际操作的平均性能，帮助我们了解在多次操作下的表现。

### 5. **均摊分析的具体类型**

均摊时间复杂度通常有几种常见的分析方法，具体选择哪种方法取决于数据结构和算法的特性。

- **聚合方法（Aggregate Method）**：这种方法是最直接的，直接计算一系列操作的总时间，然后将总时间平均到每个操作上。适用于每个操作有相似的成本，或者对每个操作都能进行较为精确的成本估计。
  
- **会计方法（Accounting Method）**：假设每个操作有一个“实际成本”和“虚拟成本”，其中某些操作会提前“支付”额外的成本，提前为昂贵操作储备费用。通过这种方法，我们可以在某些操作上“存钱”来补偿未来的昂贵操作。
  
- **潜力方法（Potential Method）**：通过引入一个潜力函数，将数据结构的状态与其潜力（类似于虚拟成本）关联起来。潜力函数可以通过降低结构复杂度来降低未来操作的成本。

### 6. **总结**

均摊时间复杂度是对一系列操作的平均时间复杂度的分析方法，它帮助我们理解在长期操作中，每个操作的“平均”成本。通过均摊分析，复杂度较高的操作（如扩容）能够被“摊销”到其他便宜的操作上，从而得出更加准确的时间复杂度估计。它对于那些偶尔发生昂贵操作但大多数操作便宜的情况（例如动态数组的扩容）非常有用，能够更真实地反映程序的性能。

不要通过代码结构去判断复杂度

1，通常对于循环n次的for循环，如果再嵌套一个相同的for循环，时间复杂度会是n平方，但是有例外的，如

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

时间复杂度就是n/1 + n/2 + n/3 +……+n/n，属于调和级数，是对数型的增长。

2，调和级数

 

要了解算法流程。