[leetcode]Binary Search Tree Iterator。什么叫平均时间复杂度为O(1)的函数？

Question

https://leetcode.com/problems/binary-search-tree-iterator/

本人比较菜，一般看到这个就只想到，这个题目要求从小到大遍历一个二叉搜索树 ，当然就是中序遍历了。但是始终搞不明白题目的要求

next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

什么叫 in average O(1) time ？

Answer 1

举个例子，分析下列代码的时间复杂度：

def arrange(arr):
    for i in range(0, len(arr)):
        while arr[i] != i:
            next_pos = arr[i]
            arr[i], arr[next_pos] = arr[next_pos], arr[i]
    return arr

print arrange([0,3,5,1,4,2])

这个代码是把长度为L，范围从0...L-1的整数数组进行排序。

虽然有循环嵌套，但是这个代码的复杂度是O(n)，因为while内的语句最多执行n-1次，所以均摊给外面的for循环，每个循环平均执行一次。也就是说while的复杂度均摊下来是O(1)的。

Answer 2

平均时间复杂度为常数，与问题复杂度（这里指树的高度）无关

Answer 3

不知道楼主怎么看出是要求中序遍历的。。

Answer 4

楼主需要补充算法的基础知识,建议先找本算法的基础教材看一遍,推荐《算法导论》