問(wèn)答題

【簡(jiǎn)答題】求最大、最小元算法的時(shí)間復(fù)雜度（比較次數(shù)）下界是多少？分治算法在什么情況下可以達(dá)到下界？

答案： 在規(guī)模為n的數(shù)據(jù)元素集合中找出最大元和最小元，至少需要3n/2-2次比較，即3n/2-2是找最大最小元算法的下界。當(dāng)n=...
題目列表

你可能感興趣的試題

問(wèn)答題

【簡(jiǎn)答題】分治法求最大、最小元算法的主要思想？
答案： 當(dāng)n=2時(shí)，一次比較就可以找出兩個(gè)數(shù)據(jù)元素的最大元和最小元。當(dāng)n>2時(shí)，可以把n個(gè)數(shù)據(jù)元素分為大致相等的兩半，一半有n/...
問(wèn)答題

【簡(jiǎn)答題】分治法的要領(lǐng)是什么？（分治法可分為哪三個(gè)主要步驟）
答案： 分治法的要領(lǐng)
分治法是把一個(gè)規(guī)模較大的問(wèn)題分解為若干個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題同類；首先...
微信掃碼免費(fèi)搜題