你可能感興趣的試題

如果f₁（n）= Θ（g₁（n））并且f₂（n）= Θ（g₂（n）），下列說(shuō)法是否正確？

求有序數(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。

求解最接近中位數(shù)的k個(gè)數(shù)：給定由n個(gè)互不相同的數(shù)組成的集合A以及正整數(shù)k≤n，設(shè)計(jì)一個(gè)O（n）時(shí)間復(fù)雜度的查找A中最接近A的中位數(shù)的k個(gè)數(shù)的算法。在采用分治法進(jìn)行查找時(shí)，為了滿(mǎn)足分治法的平衡原則，需要將數(shù)組分成兩個(gè)大小基本相同的子數(shù)組，其中的那個(gè)劃分點(diǎn)就是中位數(shù)。所以，中位數(shù)是指數(shù)組中能將數(shù)組劃分成兩個(gè)大小基本相同的兩個(gè)子數(shù)組的那個(gè)元素，即中位數(shù)是第「n／2」小的數(shù)。

求解最接近中位數(shù)的k個(gè)數(shù)：給定由n個(gè)互不相同的數(shù)組成的集合A以及正整數(shù)k≤n，設(shè)計(jì)一個(gè)O（n）時(shí)間復(fù)雜度的查找A中最接近A的中位數(shù)的k個(gè)數(shù)的算法。在采用分治法進(jìn)行查找時(shí)，為了滿(mǎn)足分治法的平衡原則，需要將數(shù)組分成兩個(gè)大小基本相同的子數(shù)組，其中的那個(gè)劃分點(diǎn)就是中位數(shù)。所以，中位數(shù)是指數(shù)組中能將數(shù)組劃分成兩個(gè)大小基本相同的兩個(gè)子數(shù)組的那個(gè)元素，即中位數(shù)是第「n／2」小的數(shù)。