問答題

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

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

你可能感興趣的試題

問答題

【簡答題】分治法求最大、最小元算法的主要思想?

答案: 當(dāng)n=2時,一次比較就可以找出兩個數(shù)據(jù)元素的最大元和最小元。當(dāng)n>2時,可以把n個數(shù)據(jù)元素分為大致相等的兩半,一半有n/...
問答題

【簡答題】分治法的要領(lǐng)是什么?(分治法可分為哪三個主要步驟)

答案: 分治法的要領(lǐng)
分治法是把一個規(guī)模較大的問題分解為若干個規(guī)模較小的子問題,這些子問題相互獨立且與原問題同類;首先...
微信掃碼免費搜題