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

问题描述

问 题

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 ？

解决方案

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

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)的。

这篇关于算法 - [leetcode]Binary Search Tree Iterator。什么叫平均时间复杂度为O(1)的函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！