Java算法設(shè)計(jì)與分析PPT第1-第9章

第1章 算法概述
學(xué)習(xí)要點(diǎn):
理解算法的概念。
理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。
掌握算法的計(jì)算復(fù)雜性概念。
掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。
掌握用C++語言描述算法的方法。
算法(Algorithm)
算法是指解決問題的一種方法或一個(gè)過程。
算法是若干指令的有窮序列，滿足性質(zhì)：
(1)輸入：有外部提供的量作為算法的輸入。
(2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。
(3)確定性：組成算法的每條指令是清晰，無歧義的。
(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。
程序(Program)
程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。
程序可以不滿足算法的性質(zhì)(4)。
例如操作系統(tǒng)，是一個(gè)在無限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。
操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問題，每一個(gè)問題由操作系統(tǒng)中的一個(gè)子程序通過特定的算法來實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止
算法復(fù)雜性分析
算法復(fù)雜性 = 算法所需要的計(jì)算機(jī)資源
算法的時(shí)間復(fù)雜性T(n)；
算法的空間復(fù)雜性S(n)。
其中n是問題的規(guī)模（輸入大�。�。