[理工] 資料結構

[j897495 (咪咪)]

A.Which sorting method is the fastest one in average case?

1.merge sort 2.heap sort 3.quick sort 4.radix sort 5.bubble sort

答案給3但是4不是linear所以可以是O(n+e)嗎?


B.randomized quicksort和quicksort的recurrence and solutin?

quicksort有分average and worst 那跟randomized差在哪呢??

是pivot比較不會是最小or最大嗎?


C.Consider the failure function defined as below.Show the values of
f(o),f(1)...,f(5) of string p0p1p2p3p4p5=ababaa

f(j)={largest 0<=i<j such that p0...pi=pj-1...pj and pi+1 != pj+1
      -1     if there is no i>=o satisfying above }

Ans:  a  b  a  b  a  a
     -1 -1  0  1  2  0

不懂這題的意思@@"

希望各位幫我解惑  先謝謝了!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.224.164
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1420981834.A.81A.html
推 A4P8T6X9: A 我記得快速排序的快取運用很好，平均很快。
→ A4P8T6X9: B 就是代表支點隨便取的 quicksort
→ A4P8T6X9: C KMP algorithm
→ j897495: thanks!
推 jeff04209: 所以A到底為啥quicksort比radix sort快? 是因為一般來
→ jeff04209: 說input值都很大嗎?
→ shanbb: 記得沒錯，實作來說quicksort在所有sort裡頭平均最快的