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
不懂這題的意思@@"
希望各位幫我解惑 先謝謝了!