問答題

【簡答題】證明：若f₁（n）=O（g1（n））并且f₂（n）= O（g2（n）），那么f₁（n）+f₂（n）= O（max{g₁（n），g₂（n）}。

答案：

你可能感興趣的試題

【計(jì)算題】求解最接近中位數(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í)，為了滿足分治法的平衡原則，需要將數(shù)組分成兩個(gè)大小基本相同的子數(shù)組，其中的那個(gè)劃分點(diǎn)就是中位數(shù)。所以，中位數(shù)是指數(shù)組中能將數(shù)組劃分成兩個(gè)大小基本相同的兩個(gè)子數(shù)組的那個(gè)元素，即中位數(shù)是第「n／2」小的數(shù)。根據(jù)b找出所要的解{|a-mid|≤b，a∈A}。

答案： {30，27，35}。

【簡答題】對(duì)算法進(jìn)行分析分哪兩個(gè)階段？各自完成什么任務(wù)（分別得到什么結(jié)果）？

答案：對(duì)一個(gè)算法要作出全面的分析可分成兩個(gè)階段進(jìn)行，即：事前分析和事后測(cè)試。
事前分析求出該算法的一個(gè)時(shí)間界限函數(shù)；...

<bdo id="gl9sw"></bdo>