平衡搜索樹查詢，漸進的分析

Question

的情況如下： -

我們有N個號碼，我們有打印 他們有序。我們訪問 來平衡字典數據結構， 它支持操作serach， 插入，刪除，最小值，最大值每個 在O（log n）時間。

我們希望在 排序順序檢索在O數量（N log n）的使用 只插入時間和順序 遍歷。

這個問題的答案是： -

Sort() 
    initialize(t) 
    while(not EOF) 
    read(x) 
    insert(x,t); 
    Traverse(t); 

現在查詢是，如果我們閱讀時的「n」的元素，然後遍歷在「日誌N」中的元素（中序遍歷）時間，那麼這個算法的總時間（n + logn）時間，根據我..請說明該算法的後續計算時間的計算方式。它將如何對列表中的O（nlogn）進行排序時間？

謝謝。

Answer 1

每個插入是O(log n)。你正在做n插入，所以給出n * O(log n) = O(n log n)漸近時間複雜度。遍歷樹是O(n)，因爲有n節點。這就增加了O(n + n log n)從O(n log n)相差一個恆定的，所以最終漸近複雜性是O(n log n) ..

然後遍歷中的元素「日誌N

遍歷是O(n)，不O(log n)。插入是O(log n)，你在做n這樣的插入。