by Mrs. Qu
已有的排序算法：考察元素比較次數(shù)
插入排序仿贬、冒泡排序：最壞和平均狀況下都為O(n2)
快速排序：最壞狀況為O(n2)，平均狀況下為O(nlogn)
堆排序枕磁、二分歸并排序：最壞和平均狀況下都為O(nlogn)
好的算法
提高求解問題的效率
節(jié)省存儲空間
需要解決的問題
問題→尋找求解算法算法設(shè)計(jì)技術(shù)
算法→算法的評價(jià) 算法分析方法
算法類→問題復(fù)雜度的評價(jià)問題復(fù)雜性分析
問題類→能夠求解的邊界計(jì)算復(fù)雜性理論
理論上的可計(jì)算：可計(jì)算理論
研究目標(biāo)
確定什么問題是可計(jì)算的岗宣，即存在求解算法
合理的計(jì)算模型
已有的：遞歸函數(shù)热某、Turing機(jī)、λ演算园细、Post系統(tǒng)等
條件：計(jì)算一個(gè)函數(shù)只要有限條指令
每條指令可以由模型中的有限個(gè)計(jì)算步驟完成
指令執(zhí)行的過程是確定的
核心論題：Church-Turing論題
如果一個(gè)函數(shù)在某個(gè)合理的計(jì)算模型上可計(jì)算惦积，那么它在
Turing機(jī)上也是可計(jì)算的
可計(jì)算性是不依賴于計(jì)算模型的客觀性質(zhì)
多項(xiàng)式時(shí)間的算法
時(shí)間復(fù)雜度函數(shù)為O(p(n))的算法，其中p(n)是n的多項(xiàng)式
不是多項(xiàng)式時(shí)間的算法不存在多項(xiàng)式 p(n)使得該算法的時(shí)間復(fù)雜度為O(p(n))猛频，包含指數(shù)時(shí)間甚至更高階的算法
多項(xiàng)式時(shí)間可解的問題P
存在著解P 的多項(xiàng)式時(shí)間的算法難解的問題P
不存在解P 的多項(xiàng)式時(shí)間的算法
實(shí)際上可計(jì)算的問題
多項(xiàng)式時(shí)間可解的問題
函數(shù)的漸進(jìn)的界
定義1.1 設(shè) f 和g是定義域?yàn)樽匀粩?shù)集 N上的函數(shù).
(1) 若存在正數(shù)c 和n0使得對一切n ≥ n0有0 ≤ f(n) ≤ cg(n) 成立, 則稱f(n) 的漸近的上界是 g(n)狮崩，記作f (n) = O(g(n)).
(2)若存在正數(shù) c 和 n0，使得對一切 n ≥ n0有 0 ≤ cg(n) ≤ f(n)成立, 則稱f(n)的漸近的下界是g(n)伦乔，記作f (n) = Ω(g(n)).
(3) 若對于任意正數(shù)c 都存在n0厉亏，使得當(dāng)n ≥ n0 時(shí)有0 ≤ f(n)< cg(n) 成立, 則記作f(n)= o(g(n)).
(4) 若對于任意正數(shù)c 都存在n0，使得當(dāng)n ≥ n0 時(shí)有0 ≤cg(n) < f(n)成立, 則記作f(n)=ω (g(n)).
(5) 若f (n) = O(g(n)) 且f (n) = Ω(g(n)), 則記作f (n)=Θ(g(n)).
例f(n)=n2+n烈和，則
f(n)=O(n2), f(n)=O(n3),
f(n)=o(n3),
f(n)=Θ(n2)
