用Strassen矩陣乘法計(jì)算乘積:
如果f1(n)= Θ(g1(n))并且f2(n)= Θ(g2(n)),下列說(shuō)法是否正確?
(a)和(c)均正確,(b)錯(cuò)誤。
求有序數(shù)組A和B的中位數(shù) 設(shè)A[0∶n-1]和B[0∶n-1]為兩個(gè)數(shù)組,每個(gè)數(shù)組中含有n個(gè)已排好序的數(shù)。設(shè)計(jì)一個(gè)O(1ogn)時(shí)間復(fù)雜度的算法,找出A和B的2n個(gè)數(shù)的中位數(shù)median。