摊销分析仅适用于数据结构吗？
Does amortized analysis applies to data structures only?
在我看到的所有地方（在 SO 和其他来源上），摊销分析通常仅适用于数据结构。例如 dynamic array or splay tree。但是，我还没有看到对纯算法进行摊销分析的应用。说算法的摊销分析有意义吗？摊销分析假定一系列操作适用于数据结构，但不适用于算法。
只有当存在某种可变状态允许在一个操作中完成的计算影响另一个操作中的计算性能时，摊销一系列操作的成本才有意义。如果一系列操作的性能可以独立分析为单个操作的性能总和，每个操作不依赖于其他执行的操作，则不会进行摊销。
所以从这个意义上说，摊销分析只适用于数据结构，而不适用于纯算法。然而，这假设了一个非常广泛的“数据结构”定义，它实际上涵盖了任何可变状态。例如，coroutine 的局部变量在协程暂停执行时仍然存在，是否应被视为数据结构是值得商榷的。
同样，我们通常不会考虑使用 LRU cache to "be" a data structure, rather we would say it "uses" a data structure for the cache, and when analysing the performance of a series of invocations (some of which hit the cache, others of which miss), we wouldn't say that we're analysing the data structure the cache uses, we'd say we're analysing a memoised 算法修饰的函数。
在许多字符串算法中，您使用摊销来分析 运行 时间。例如在线性时间内构建边界数组或后缀树，或者从后缀数组遍历模拟后缀树。
后缀树和后缀数组当然是数据结构，但是您不使用通常意义上的摊销将一系列修改的成本相加；您在构建它们或遍历它们的算法时使用它。您将有一些昂贵的步骤和一些便宜的步骤，摊销可以更容易地计算总 运行 时间。
通常，您在很难限制每个步骤所用时间的算法中使用它，因为它可能取决于数据，但您可以通过各种摊销参数限制总数。你在我最熟悉的字符串算法中做了很多，但它到处都是。
当然，只有当你必须从一些明确定义的起点进行一系列操作时才有意义（这样你就不会从昂贵的操作开始然后停止）。但是除了修改数据结构还有更多的应用。
在我看到的所有地方（在 SO 和其他来源上），摊销分析通常仅适用于数据结构。例如 dynamic array or splay tree。但是，我还没有看到对纯算法进行摊销分析的应用。说算法的摊销分析有意义吗？摊销分析假定一系列操作适用于数据结构，但不适用于算法。
只有当存在某种可变状态允许在一个操作中完成的计算影响另一个操作中的计算性能时，摊销一系列操作的成本才有意义。如果一系列操作的性能可以独立分析为单个操作的性能总和，每个操作不依赖于其他执行的操作，则不会进行摊销。
所以从这个意义上说，摊销分析只适用于数据结构，而不适用于纯算法。然而，这假设了一个非常广泛的“数据结构”定义，它实际上涵盖了任何可变状态。例如，coroutine 的局部变量在协程暂停执行时仍然存在，是否应被视为数据结构是值得商榷的。
同样，我们通常不会考虑使用 LRU cache to "be" a data structure, rather we would say it "uses" a data structure for the cache, and when analysing the performance of a series of invocations (some of which hit the cache, others of which miss), we wouldn't say that we're analysing the data structure the cache uses, we'd say we're analysing a memoised 算法修饰的函数。
在许多字符串算法中，您使用摊销来分析 运行 时间。例如在线性时间内构建边界数组或后缀树，或者从后缀数组遍历模拟后缀树。
后缀树和后缀数组当然是数据结构，但是您不使用通常意义上的摊销将一系列修改的成本相加；您在构建它们或遍历它们的算法时使用它。您将有一些昂贵的步骤和一些便宜的步骤，摊销可以更容易地计算总 运行 时间。
通常，您在很难限制每个步骤所用时间的算法中使用它，因为它可能取决于数据，但您可以通过各种摊销参数限制总数。你在我最熟悉的字符串算法中做了很多，但它到处都是。
当然，只有当你必须从一些明确定义的起点进行一系列操作时才有意义（这样你就不会从昂贵的操作开始然后停止）。但是除了修改数据结构还有更多的应用。