假設我有一個像[5, 3, 1, 2, 4]這樣的元素列表，我想按位置比較兩個元素。列表中的第一個更大，或者true。所以：如何在恆定時間比較列表中的兩個元素
compare(5, 3) # true
compare(2, 1) # false
compare(3, 4) # true
我該如何在恆定時間內做到這一點？一種方式我認爲這樣做是使用地圖，其中關鍵的是元素的和值在列表中的位置：
order = {5: 0, 3: 1, 1: 2, 2: 3, 4: 4}
然後我們攤銷O（1）時間，但這將是O（ N）空間。有沒有人有更優雅的解決方案？
您的地圖創意看起來不錯。內存映射爲O（N）的事實不應該成爲問題，因爲除非使用壓縮技術（列表也是O（N）），否則不能得到小於O（N）的值。
此外，由於地圖存儲每個元素的索引，因此您可能會忘記原始列表，並只使用地圖。也就是說，除非你出於某種原因需要清單。即使你需要在中間插入一個元素（比如在位置3），你可以通過迭代元素並遞增必要的索引來在線性時間內更新地圖。
因此，該映射看起來像基本操作列表一樣有效，同時增加了O（1）比較函數的可怕性。至於優雅，地圖很難打敗，因爲它不需要超出這裏所描述的額外工作。
如果非要從列表中開始，你只是做操作了幾下，使用方法：
def compare(ls, n1, n2):
return ls.index(n1) > ls.index(n2)
如果你可以事先選擇的表示，或者如果你需要做很多次用同樣的名單，做你對字典所做的事情。
還請記住，該列表使用O（N）空間，因此字典的O（N）空間的添加沒有什麼大不了的。
修正：上面的比較功能將需要O（1）時間，因爲在python取O（1）時間訪問，看到http://wiki.python.org/moin/TimeComplexity
你能勾勒出潛在的業務問題？ – mellamokb 2011-02-17 23:26:41