軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2022/8/24）在線測(cè)試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/8/24

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2022/8/24）

試題四
閱讀以下說(shuō)明和圖，填補(bǔ)流程圖中的空缺。
【說(shuō)明】
在一條農(nóng)村公路的一邊稀疏地分布著房子，其分布如圖10-5所示。某電信公司需要在某些位置放置蜂窩電話基站，由于基站的覆蓋范圍是6公里，因此必須使得每棟房子到某個(gè)基站的直線距離不超過(guò)6公里。為簡(jiǎn)化問題，假設(shè)所有房子在同一直線上，并且基站沿該直線放置。現(xiàn)采用貪心策略實(shí)現(xiàn)用盡可能少的基站覆蓋所有的房子。

實(shí)現(xiàn)貪心算法的流程如圖10-6所示，請(qǐng)?zhí)畛淦渲锌瞻撞⒂?jì)算該算法的時(shí)間復(fù)雜度，其中：
1．d[i](1≤i≤N)表示第i個(gè)房子到公路A端的距離，N表示房子的總數(shù)，房子的編號(hào)按照房子到公路A端的距離從小到大進(jìn)行編號(hào)。
2．s[k]表示第k(k≥1)個(gè)基站到公路A端的距離，算法結(jié)束后k的值為基站的總數(shù)。


該算法的時(shí)間復(fù)雜度為  (5)  。