第2章算法復(fù)雜度2024/11/91主要內(nèi)容●算法●算法的復(fù)雜度

●常見的復(fù)雜度2.1算法算法(algorithm)就是一個正確的計算過程，該過程取某個值或值的集合作為輸入并產(chǎn)生某個值或值的集合作為輸出。2024/11/922024/11/93算法的4個主要特性：2.1算法算法的4個主要特性是：●確切性：算法由語句組成，每個語句的功能是確切的。●輸入數(shù)據(jù)：可以向算法輸入多個或0個數(shù)據(jù)（方法可以有參數(shù)或無參數(shù)），即算法可以接收或不接收外部數(shù)據(jù)?！褫敵鰯?shù)據(jù)：算法可以給出明確的計算結(jié)果（方法的返回值）或輸出若干數(shù)據(jù)到客戶端以反映算法產(chǎn)生的效果。●可行性：基本操作都是在有限時間內(nèi)被完成。所謂有限時間是指這個時值僅僅依賴于特定的硬件設(shè)施，不依賴于一個正整數(shù)n，即不會隨著n的增加而增大?！翊_切性●輸入數(shù)據(jù)●輸出數(shù)據(jù)●可行性2024/11/94一個算法不能在有限的時間內(nèi)結(jié)束，就不屬于算法復(fù)雜度的研究的范疇，比如一個算法里出現(xiàn)的無限循環(huán)，就不再屬于算法復(fù)雜度的研究的范疇了2.2復(fù)雜度算法，從執(zhí)行到結(jié)束，涉及兩個度量：一個是執(zhí)行方法所消耗的時間，一個是執(zhí)行方法所需要的內(nèi)存空間。2024/11/95方法里聲明的局部變量，包括參數(shù)都不歸類到基本操作，即不是基本操作。2.2復(fù)雜度⒈基本操作一個基本操作是一個語句或一個運算表達式。一個基本操作是一個語句或一個運算表達式，而且必須是在有限時間內(nèi)能被完成的計算步驟，其耗時僅僅依賴于特定的硬件設(shè)施，不依賴于一個正整數(shù)n，不會隨著n的增加而增大。2024/11/96在計算算法執(zhí)行的基本操作的總數(shù)時，要真對最壞的情況，即在某種條件下執(zhí)行的基本操作的總數(shù)是最多的情況2.2復(fù)雜度3時間復(fù)雜度算法執(zhí)行的基本操作的總數(shù)T(n)。算法的復(fù)雜度主要是度量隨著n的增大，T(n)值的趨勢。2024/11/97學(xué)習復(fù)雜度，記住一個通俗的道理：時間累加，空間不累加.2.2復(fù)雜度4復(fù)雜度比較2024/11/982.3常見復(fù)雜度⒈O(jiān)(1)復(fù)雜度算法中的基本操作被執(zhí)行的總次數(shù)是一個常量，即不依賴一個正整數(shù)n、不會隨著n的增加而增大，那么將算法的時間復(fù)雜度，記作O(1)。算法中的所占用的內(nèi)存是一個常量，即所占內(nèi)存不依賴一個正整數(shù)n、不會隨著n的增加而增大，那么將算法的空間復(fù)雜度，記作O(1)。

例子1Max.javaExample2_1.java2024/11/992.3常見復(fù)雜度1.O(1)復(fù)雜度

例子2Sum.javaExample2_2.java2024/11/9102.3常見復(fù)雜度2.O(n)復(fù)雜度

2024/11/9112.3常見復(fù)雜度2.O(n)復(fù)雜度例子3SumAndMult.java

Example2_3.java

2024/11/9122.3常見復(fù)雜度2.O(n)復(fù)雜度例子4ArrayMax.java

Example2_4.java

2024/11/9132.3常見復(fù)雜度2.O(n)復(fù)雜度例子5FindMissNumber.java

Example2_5.java

理論上知道，同一臺計算機，執(zhí)行“異或”運算要比“加減”運算快。所以，對于同一個算法，在復(fù)雜度相同的情況下，盡量使用速度快的基本操作。如果軟件的需求不十分介意速度，選擇的基本操作能使得的代碼更簡練、閱讀性更好，那么也可以使用這樣的基本操作。2024/11/9142.3常見復(fù)雜度3.2024/11/9152.3常見復(fù)雜度3.例子6Multi.java

Example2_6.java

2024/11/9162.3常見復(fù)雜度3.例子7BubbleSort.java

Example2_7.java

2024/11/9172.3常見復(fù)雜度4.

2024/11/9182.3常見復(fù)雜度4.例子8OutPutNumber.java

Example2_8.java

2024/11/9192.3常見復(fù)雜度5.

2024/11/9202.3常見復(fù)雜度5.例子9FindNumber.java

Example2_9.java

2024/11/9212.3常見復(fù)雜度5.例子10Euclidean.java

Example2_10.java

2024/11/9222.3常見復(fù)雜度6.

如果一個方法里又調(diào)用了其它方法，即一個算法又包含另外一個算法，那么該方法的復(fù)雜度將和它包含的方法復(fù)雜度有關(guān)，需合并考察復(fù)雜度。

2024/11/9232.3常見復(fù)雜度6.例子11DataInArray.java

Example2_11.java

2024/11/9242.3常見復(fù)雜度6.例子12GCDInArray.jav