伸展樹最壞情況下搜索時間

由於伸展樹是一種不平衡二叉搜索樹（brilliant.org/wiki/splay-tree）的，它不能保證的高度至多爲O（log（n））的。因此，我認爲它不能保證O（log（n））的最壞情況搜索時間。伸展樹最壞情況下搜索時間

伸展樹具有O（的log（n））的最壞的情況下搜索時間???

2017-10-10 NoName

維基百科頁面清楚地表明_amortized_訪問成本爲O（log n），但任何單獨的訪問都可以是O（n）。攤銷範圍很常見。在許多語言中動態增長的'ArrayList's具有分攤的O（1）插入開銷，但是任何單獨的插入都可能需要O（n）時間，因爲整個數組必須複製到一個新的更大的內存塊中。 – Gene

你是對的;對於不平衡樹，查找樹中查找的成本可以達到Θ（n）。

許多像big-O備忘單這樣的資源要麼做簡化的假設，要麼只是事實上有不正確的數據。目前還不清楚他們在這裏是否只是錯誤，或者他們是否在談論分期付款最壞的情況等等。

最好了解您正在使用的數據結構的內部，以便了解運行時間來自哪裏。

2017-10-10 05:00:24 templatetypedef

回答