问摊销分析是否仅适用于数据结构？

EN

只有当存在某种可变状态，允许在一个操作中完成的计算影响另一个操作中的计算性能时，摊销一系列操作的成本才有意义。如果一系列操作的性能可以独立地分析为各个操作的性能总和，其中每个操作都不依赖于执行的其他操作，则不会进行摊销。

因此，从这个意义上说，摊销分析只适用于数据结构，而不适用于纯算法。然而，这假设了一个非常宽泛的“数据结构”的定义，它几乎涵盖了任何可变状态。例如，当协程执行暂停时，coroutine的局部变量是否应该被视为数据结构，这是有争议的。

同样，我们通常不会将装饰有LRU cache的函数视为“是”数据结构，而是说它“使用”缓存的数据结构，并且在分析一系列调用(其中一些命中缓存，另一些未命中)的性能时，我们不会说我们正在分析缓存使用的数据结构，我们会说我们正在分析memoised算法。

在许多字符串算法中，您使用摊销来分析运行时间。例如在线性时间内构建边界数组或后缀树，或者从后缀数组遍历模拟的后缀树。

后缀树和后缀数组当然是数据结构，但您不会使用通常意义上的摊销，即将一系列修改的成本相加；您可以在构造它们或遍历它们的算法时使用它。您将有一些昂贵的步骤和一些廉价的步骤，而且摊销使计算总运行时间变得更容易。

通常，在很难限定每个步骤所用时间的算法中使用它，因为它可以依赖于数据，但您可以通过各种摊销参数来限定总时间。你在字符串算法中做了很多事情，我最熟悉的是字符串算法，但它到处都是。

当然，只有当您必须从某个定义明确的起点执行一系列操作时，它才有意义(这样您就不会从昂贵的操作开始，然后停止)。但是，除了修改数据结构之外，还有更多的应用。