是的,可以。摊销复杂度考虑了最坏情况出现的频率。因此,只要最坏情况在大约1个N²次操作中出现一次,摊销复杂度就会是常数。我们来举个简单的例子——动态扩展数组(我将其称为vector,因为在大多数语言中都是这样称呼)。在大多数情况下,向后推一个元素的时间是恒定的。大多数情况下,推送元素是一个简单的赋值操作,但偶尔会分配所有分配的元素,我们需要重新分配vector。这将是push_back操作的最坏情况,当发生这种情况时,操作的时间复杂度是线性的。但是,vector增长的方式确保重新分配的频率不太频繁。每次vector重新分配时,它的大小都会加倍。因此,在另一次重新分配之前,我们将进行n个简单的push_back操作(假设n是重新分配之前的vector容量)。因此,线性复杂度的最坏情况最多出现一次。类似于上面的情况,想象一种数据结构,在O(n²)内重新分配,但确保重新分配在n²个常数操作内最多执行一次。这将是具有摊销复杂度O(1)和最坏情况复杂度O(N²)的操作的示例。