算法解題思路是什么

分析框架

1、以算法輸入規(guī)模n作為參數(shù)進行分析算法效率

2、時間復(fù)雜度：找出基本操作O(1)，再計算它的運行次數(shù)（忽略乘法常量，僅關(guān)注增長次數(shù)）

3、增長次數(shù)：log2n

4、最差、平均和最佳效率均是指輸入規(guī)模為n時候的效率（平均效率可以引用已知的推到結(jié)果）

主要概括分析框架：

1、算法的時間效率和空間效率都用輸入規(guī)模的函數(shù)進行度量。

2、用算法的基本操作的執(zhí)行次數(shù)來度量時間效率，用算法消耗的額外單位的數(shù)量來度量空間單位

3、在輸入規(guī)模相同的情況下，有寫算法的效率會有顯著的差異，對于這類算法需要分析最差、平均和最佳效率

4、框架主要關(guān)心：輸入規(guī)模趨向于無限大的情況下它的效率問題

漸近符號和基本效率類型

1、O(g(n))是增長次數(shù)

2、Ω(g(n))是增長次數(shù) >= c*g(n)的函數(shù)集合，下階

3、θ(g(n))是增長次數(shù) = c*g(n)的函數(shù)集合，同階

可以利用極限進行比較增長次數(shù)（洛必達(dá)法則）算法整體效率是由具有較大增長次數(shù)的部分所決定的。

非遞歸問題的數(shù)學(xué)分析的通用方案

1、決定哪個參數(shù)表示輸入規(guī)模的度量標(biāo)準(zhǔn)

2、找出算法的基本操作

3、檢查基本操作的執(zhí)行次數(shù)是否只依賴于輸入規(guī)模，如果它還依賴于一些其他的特性（例如：元素在數(shù)組中的位置等）則分析最差、平均和最佳效率

4、建立一個算法基本操作執(zhí)行次數(shù)的求和表達(dá)式（有可能是遞推表達(dá)式）

5、利用求和運算的標(biāo)準(zhǔn)運算或者法則來建立一個操作次數(shù)的閉合公式，或者至少確定它的增長次數(shù)

遞歸問題的數(shù)學(xué)分析的通用方案

1、決定哪個參數(shù)表示輸入規(guī)模的度量標(biāo)準(zhǔn)

2、找出算法的基本操作

3、檢查基本操作的執(zhí)行次數(shù)是否只依賴于輸入規(guī)模，如果它還依賴于一些其他的特性（例如：元素在數(shù)組中的位置等）則分析最差、平均和最佳效率

4、對于算法基本操作執(zhí)行次數(shù)，建立一個遞推關(guān)系以及相應(yīng)的初始條件。

5、解這個遞推式，或者至少確定它的增長次數(shù)。