設置時間和速度的複雜性

我正在刷新算法和數據結構，並且有幾個問題以及我希望您檢查的語句。 O（1）（size，get，set，...），O（n） - 添加操作。
LinkedList - 所有操作O（1）（包括add（）），除了檢索第n個元素是O（n）。我假設size（）操作也在O（1）中運行，對吧？設置時間和速度的複雜性

TreeSet - 所有操作O（lg（N））。 size（）操作需要O（lg（n）），對嗎？

HashSet - 所有操作O（1）如果使用了正確的散列函數。
HashMap - 所有操作O（1），與HashSet同源。

任何進一步的解釋是非常受歡迎的。先謝謝你。

來源

2011-07-09 Anton K.

如果你有這樣的魔力HashSet的，爲什麼你需要的ArrayList？ –

@Stas：因爲一個List和一個Set不是一回事，而且因爲常數因素仍然可能有很大的不同...... –

@Stas：這個命令只能讓你知道操作是如何擴展的。它不會告訴你這個因素，例如HashSet可能比ArrayList慢許多倍，並且沒有get（）/ set（）方法。 –

ArrayList.add()是攤銷 O（1）。如果操作不需要調整大小，則爲O（1）。如果它確實需要調整大小，它是O（n），但大小然後增加，以便下一個調整大小不會發生一段時間。

從Javadoc：

增加操作運行在分期常量時間，也就是，加入n個元素需要O（n）的時間。所有其他操作都在線性時間內運行（粗略地說）。與LinkedList實現相比，常數因子較低。

就性能分析而言，該文檔對於Java集合來說通常相當不錯。

散列算法的O（1）不是僅僅應用「合適的」散列函數的問題 - 即使散列函數非常好，也可能碰巧發生散列衝突。通常的複雜度是O（1），但當然它可以是O（n），如果所有哈希碰巧碰撞。

來源

2011-07-09 13:02:23

+1：同樣，LinkedList是O（1），只要它不觸發GC，它更可能做到這一點。 ;） –

「它不觸發GC」？ –

@Suraj：GC =「垃圾回收」（？） – abeln

請訪問以下鏈接。它會幫助你清除疑惑。

來源

2011-07-09 13:13:58

設置時間和速度的複雜性

回答

相關問題