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

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