0

我如何进行摊销分析并证明后继函数（在中序算法中找到下一个元素的函数）平均为 O(1)？假设后继函数对找到的最后一个元素进行操作。甚至是 O(1) 吗？是 O(log n) 吗？

4

1 回答 1

0

一种思考方式是后继函数的N个应用程序遍历整个树。遍历整棵树的复杂度是多少？在N个函数调用中摊销是什么？

于 2017-12-13T14:24:05.703 回答