零、主定理
零-零、利用數(shù)學(xué)方法求解遞歸式
一、歸并排序
*二、最大子數(shù)組問題
2.1 問題描述
2.2 使用分治策略求解
2.3 分治法的分析
三、矩陣乘法的Strassen算法
3.1 普通矩陣乘法
3.2 一個(gè)簡(jiǎn)答的分治算法
3.3 Strassen方法

在分治策略中，遞歸地求解一個(gè)問題，在每層遞歸中應(yīng)用如下三個(gè)步驟：
1）分解：將問題劃分為一些子問題，子問題的形式與原問題一樣，只是規(guī)模更小
2）解決：遞歸地求解出子問題。如果子問題的規(guī)模足夠小，則停止遞歸，直接求解。
3）合并：將子問題的解組合成原問題的解

分治有兩種情況：
1）當(dāng)子問題足夠大，需要遞歸求解時(shí)，稱之為遞歸情況
2）當(dāng)子問題變得足夠小，不再需要遞歸時(shí)，進(jìn)入基本情況

零、主定理

主定理的三種情況分別對(duì)應(yīng)以下三種情況：
1）樹的總代價(jià)由葉節(jié)點(diǎn)的代價(jià)決定
2）樹的總代價(jià)均勻分布在樹的所有層次上
3）樹的總代價(jià)由根節(jié)點(diǎn)的代價(jià)決定

主定理的證明：（需要用到下面兩個(gè)引理）

引理4.2：

引理4.2的證明：

引理4.3：

4.3的證明：

主定理的應(yīng)用：

幾個(gè)遞歸公式的解：
1）T (n) = T (αn) + T ((1 ? α)n) + n 的解為：T (n) = Θ(n lg n)
可以用代入法驗(yàn)證
2）T (n) = T (n ? 1) + n的解為：T (n) = Θ(n2)

3）T (n) = T (√n) + 1 的解為：T(n) = Θ(lglgn)

4）T (n) = T (n/2) + T (n/4) + T (n/8) + n的解為：T(n) = Θ(n)
可以用代入法驗(yàn)證

5）T (n) = T (n ? 1) + lg n的解為：T (n) = Θ(n lg n)
6）T (n) = T (n ? 1) + 1/n的結(jié)尾：T(n) = Θ(lgn)

零-零、利用數(shù)學(xué)方法求解遞歸式

一、歸并排序

二、最大子數(shù)組問題

2.1 問題描述

股票的買入賣出，使得收益最大
暴力求解方法：嘗試每隊(duì)可能的組合，共有n(n - 1) /2種，運(yùn)行時(shí)間為Ω(n2)

問題轉(zhuǎn)換：不從每日價(jià)格的角度去看待輸入，二十考察每日價(jià)格變化，第i天的價(jià)格變化定義為第i天和第i-1天的價(jià)格差，將該數(shù)組定義為A。那么問題就轉(zhuǎn)換為尋找A的和最大的非空連續(xù)子數(shù)組。稱之為最大子數(shù)組。
只有當(dāng)數(shù)組中包含負(fù)數(shù)時(shí)，最大子數(shù)組問題才有意義，否則整個(gè)數(shù)組和肯定是最大的。

2.2 使用分治策略求解

考慮求解子數(shù)組A[low..high]的最大子數(shù)組。
使用分治技術(shù)意味著將子數(shù)組劃分為兩個(gè)規(guī)模盡量相等的子數(shù)組，比如中央位置mid。A[low..high]的任何連續(xù)子數(shù)組A[i..j]所處的位置必然是一下三種情況之一：