推 jelove:我覺得第三題應該是樹高吧@@ 03/08 01:31
→ wadekobe324:謝謝辛苦的解答~~~ 03/08 01:50
※ 引述《wadekobe324 (歐)》之銘言：
: 1.which sorting algorithm has best performance when the given data is
: nearly sorting ?
: (a) selection sort
: (b) insertion sort
: (c) bubble sort
: (d) heap sort
應該是b or c
紅兔講義上是說
在best case下(Data遞增排列)
insertion sort與bubble sort
都只要做(n-1)次比較
無任何SWAP發生
故Time Complexity = O(n)
但後來我在想
如果是nearly sorting情況下
Bubble sort也許會多一次檢查(for迴圈)
所以我會猜(b)
: 2.if we only count the data movement, which of the following sorting algorithm
: has the best time complexity ?
: (a) quick sort
: (b) merge sort
: (c) heap sort
: (d) insertion sort
: (e) selection sort
不確定
我會選(e)
(a)(b)(c)感覺 data movement都會很多次
假設{4,3,2,1}
(d)
Pass1:{3,4,2,1} 2次move
Pass2:{2,3,4,1} 3次move
Pass3:{1,2,3,4} 4次move
(e)
Pass1:{1,3,2,4} 1次swap
Pass2:{1,2,3,4} 1次swap
尤其當 data 數目很多
我是覺得selection sort應該會有最少的 data movement
: 3.what is the average time complexity to search in a Min-heap data structure?
我只知道找min是O(1) =_="
這需要高手指導
: 4.what is the worst case time complexity to search in a binary search tree?
這題紅兔講義有
當B.S.T是 Skewed B.S.T時
search time complexity is O(n)
: 5.(T/F)There are sorting algorithms that have O(N) worst case time complexity
我猜 true
因為紅兔講義上是寫說
若排序技巧並非使用 Comparison-based Skill
則有可能突破Ω(nlong)之時間限制
達到linear time
: 6.(T/F)The worst case time complexity of Dijstra's shortest path algorithm
: is O(n^3)
我猜 false
講義上只有寫
Dijkstra's Algo Time Complexity 是 O(n^2)
所以我也不清楚
worst case下 time complexity 長怎樣@@"
: 7.what data structure is needed if we want to implement a priority queue with
: O(log n) performance both for insertion and deletion
講義有
是Heap
: 這些時間複雜度這邊不是很懂~~~手邊的資料又找不太到~~
: 麻煩高手幫解答一下~~~感恩!!!
我超弱
只有幾題講義上有的答案確定
其他都不會>"<
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.248.217.215