假设给定一个已经排序的整数列表,例如(1,7,13,14,50).应该注意的是,该列表将不包含重复项.

是否有一些数据结构可以存储此数据,同时允许我在恒定时间内添加任何新元素(在适当的位置)？ add(10)将产生(1,7,10,13,14,50).

同样,我是否能够更新元素(例如将7更改为19)并在恒定时间内相应地改变顺序？ change(7,19)产生(1,13,14,19,50).

对于一个类,我需要编写一个尽快执行这些操作的数据结构,但是我只想知道是否可以进行恒定时间,如果不能完成,那么理想的运行时间将是多少？

解决方法:

为了以固定时间O(1)插入,对于任何数据结构,这只会作为最佳情况发生.哈希表通常具有最佳的插入时间,但是如果存在冲突并且存在单独的链接,则哈希表可能并不总是O(1).您不对散列进行排序,因此复杂性是无关紧要的.

二叉树的插入时间很好,此外,插入新节点时已经对其进行了排序.但是,这平均需要O(logn)时间.如果树为空,则插入的最佳情况是O(1).

这些仅是几个示例,有关这些操作的复杂性,请参见此处：http://bigocheatsheet.com/