平摊复杂度

平摊复杂度（Amortized Complexity）是一种在计算复杂度时使用的技术，用于描述算法在多次运行中的平均性能。平摊复杂度能够将一次性计算的复杂度分摊到多次运行中，从而更准确地衡量算法在实际应用中的性能。
平摊复杂度的计算方法通常是：将算法在每次运行中的复杂度除以运行次数，得到平均每次运行的复杂度。
在实际应用中，平摊复杂度常常用于分析并优化算法性能。例如，在分布式计算、数据库操作、缓存策略等领域，平摊复杂度有助于找出性能瓶颈，并为优化方案提供依据。
场景举例：
假设有一个任务需要执行 n 次操作，每次操作的复杂度为 O(f(n))。如果这个任务需要执行 10 次，那么总的复杂度就是 O(f(n) 10)。但如果任务可以并行执行，每次操作的复杂度降低为 O(f(n/10))，那么总的复杂度就变为 O(f(n/10) 10)。在这种情况下，尽管每次操作的复杂度没有改变，但平摊复杂度却降低了。
Demo：
为了更直观地理解平摊复杂度，我们可以通过一个简单的例子来说明。假设有一个任务需要将 100 个数相加，每次操作的复杂度为 O(1)。
方法 1：顺序计算
如果使用顺序计算的方法，需要进行 100 次加法操作，总的复杂度为 O(1) 100 = O(100)。
方法 2：并行计算
如果使用并行计算的方法，每次操作可以将 10 个数相加，总共需要进行 10 次加法操作，每次操作的复杂度为 O(1) 10 = O(10)。在这种情况下，平摊复杂度为 O(1) * 10 / 10 = O(1)。
通过这个例子，我们可以看到并行计算方法虽然一次性操作的复杂度没有改变，但由于将操作分摊到多次运行中，总的复杂度得到了降低，从而提高了算法的性能。