綠的傢俱

[DS] 交大資工資料結構期中考題a priority queue can be implemented in sorted array,unordered linked listand heap ，請問search for x, delete x,insert x,output in order的timecomplexity分別為多少??> in sorted array:> O(lgn), O(1), O(n), O(1) ^^^ 恩 應該是O(n)題目是priority queue的實作應用..因此刪除部份一定必定是刪除最大or最小的element所以一定是在陣列的兩端其中一個 所以是O(1)Ouput order部份我後來想應該也是O(n)..當初會寫O(1)是因為順著output或著逆著output就可以了.不過還是要n次step所以O(n)> in unordered linked list:> O(n), O(n), O(1), O(nlogn) ^^^^^^^^^如果直接在linked list ouput order的話那應該是O(n^2)吧 會想O(nlogn)是因為想說n個step把linked list 依照順序存到一個array在用quick sort排序 不過題目重新思考了一下  應該不能這樣作吧@@> in heap:> search : O(1) or O(lgn) [假設x每次都是搜尋max or min 就會O(1)@@]> O(lgn), O(lgn), O(nlgn)heap 這邊的search 當初應該是寫說O(1) or O(n) @@因為heap通常用array實作 也是可以search 其他key值吧@@"只是就等於 unorder array 搜尋的Time Complexity .msgcontent .wsharing ul li { text-indent: 0; } 分享 Facebook Plurk YAHOO! .