算法設(shè)計與分析問答題每日一練(2020.06.07)

問答題
求下列函數(shù)的漸近表達式：n2+10n-1；14+5/n+1/n2；
答案：①因為：；由漸近表達式的定義易知：
n²是n²+10n-1的漸近表...
問答題
假設(shè)列表的可能值屬于集合{a，b，c，d}，用分布計數(shù)算法對列表b，c，d，c，b，a，a，b按照字母順序排序.
答案：
問答題
分治法所能解決的問題一般具有什么特征？
答案：（1）該問題的規(guī)模縮小到一定的程度就可以容易地解決；
（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題...
問答題
敘述分治算法和動態(tài)規(guī)劃算法的基本思想，并比較兩種算法的異同。
答案：兩者都是遞歸算法思想的應(yīng)用，根本策略是找出大規(guī)模問題與小規(guī)模子問題之間的關(guān)系，直到小規(guī)模的子問題容易得到解決，再由小規(guī)模...
問答題
什么是平攤分析？平攤分析常用的手法有哪幾種？簡單說明這幾種手法的要點。
答案：考慮n條指令執(zhí)行的最壞時間復(fù)雜性。即使某些指令執(zhí)行時具有比較大的代價，但利用平攤分析后對整體考慮，可以得到較小的平均代價...