??????一個算法的要求有四個：有輸入、有輸出、有限性、確定性。

?????? 有一個很著名的公式是程序=數據結構+算法。由該式子能看出算法和程序的關系，算法是一段有限序列能夠解決一個問題，是解決問題的方法。程序是一個實在的東西，能夠解決一個問題。算法和程序相比，算法強調的是方法，所以算法不拘泥于各種編程語言，沒有嚴格的語法要求，在本課程中算法使用偽代碼來表示（偽代碼的使用格式在本文文末）。

??????衡量算法好壞的兩個標準是算法使用的時間和占用的空間，但隨著科技不斷進步，硬件設備的存儲空間不斷增大，空間比重相對較小。但在一些嵌入式設備中占用的空間卻是第一要考慮的因素，但本課程中只是考慮使用的時間，所以對于空間不加贅述。

??????在算法中使用時間的主要是基本操作，并且在本課程中基本操作主要包括兩種：比較操作和賦值操作。以比較和賦值的次數多少作為衡量算法好壞的標準。其中在大量復雜算法中包含兩類簡單算法：查找和排序。這兩種算法在上學期的數據結構課程中都已經學習過部分，但當時并未強調所用時間。查找排序數據主要的存儲方式是數組，在這兩類算法中數據排列的方式對于算法的好壞起著一定的決定作用，下面就以幾個具體的例子來進行說明。

1. 二分搜索

??????二分搜索也叫折半查找，是要求數據有序的前提下，每次減少一半的查找數量。

??????數據的比較次數范圍是：1~log(n)向下取整加一

2. 合并有序表：

??????合并有序表是指定兩個標記，將標記中較小或較大的數字存在臨時的輔助空間中，達到最終排序的目的。假設兩段數據長度分別為n1 和n2，并且n1是較小的部分.
?????? 數據的比較次數是：n1~n1+n2-1
?????? n1是當前一段數據的最大值小于后一段數據的最小值的情況。例如：n1(1,2,3)，n2(4,5,6,7)。n1+n2-1是當兩段數據中的元素交叉大小的時候。例如：n1(1,3,5,7)，n2(2,4,6,8)。
??????數據的賦值次數是：2（n1+n2）

3. 選擇排序

??????選擇排序是從第一位開始，選擇后面數據中最小的那個數據，與當前的數據進行位置交換。
??????數據的比較次數是：n-1~n(n-1)/2
??????n-1是數據已經是想要的順序，每一步比較一次即可.n(n-1)/2是當數據逆序有序時后的情況，這種情況下每兩個數據都要比較一次.
??????數據的賦值次數是：0~3(n-1)
??????賦值次數的最好最壞情況分別對應于比價的最好最壞情況，已經有序無須做任何交換，逆序需要交換(n-1)次，并且每兩個數據交換就要進行三次賦值操作

4. 插入排序：

??????插入排序是從第二個起，尋找該元素在前面元素中正確的位置，并將該元素插入進去。同時每次比較要將被比較元素向后移位

??????數據的比較次數是：n-1~n(n-1)/2
??????n-1是數據已經有序，每次直接向后移位。(n-1)n/2是逆序有序，每個元素都要與之前的所有元素進行比較。

??????數據的賦值次數：數據的比較次數加上n-1
??????數據的賦值包括比較元素的最終賦值以及過程中被比較元素依次向后移位，總體上看，比較次數在加n-1即為賦值次數

5. 向上合并排序：

?????? 將相鄰的2的i次方個元素每次合并為一段元素，并對這段元素使用歸并排序使之有序。最后使整體有序。
??????數據比較次數:n*log(n)/2~nlog(n)-n+1
??????最好情況對應于merge過程中的最好情況，即第一個序列的最大值小于第二個序列的最小值，最壞情況對應于merge過程中兩序列交叉的最壞情況。總體來說比較分為logn層
??????賦值次數：2nlogn次

??????前文指出，衡量算法的依據就是算法運行的時間，專業名詞叫“時間復雜度”。求解時間復雜度是一項困難的工作，因為在算法中隨著輸入序列的變化分為最好情況和最壞情況。所以沒有確切的公式去計算具體的值。于是采用漸近線的思想，類似于一種貼近，把時間復雜度用框架框起來。使用如下符號作為框架中的各個標準：

1) 大O符號

??????大O符號意思就是時間復雜度的上界，類似于最壞情況，該算法的時間復雜度永遠小于大O，舉例：㏒n = O(n)

2) 大ω符號

??????大ω符號意思是時間復雜度的下界，類似于最好情況，該算法的時間復雜度永遠大于大ω，舉例n = ω(㏒n)

3) θ符號

??????若一個算法的大O符號，大ω符號中的函數是同一個函數，則用θ來表示，同時可以用θ來表示時間復雜度。

??????對于大O符號和大ω符號，常表示之間的階數相差不大。上界和下界的表示是相對的，也可用小寫來進行表示，小寫一般代表階數相對較大，距離㏒n = o(n2), n㏒n = 小ω（㏒n）

??????對于空間復雜度研究的不多，但需要牢記，計算空間復雜度的時候不算輸入數據所占有的空間，只計算算法過程中，使用的臨時變量或者輔助數組所占的空間。

最優算法：

??????最優算法不是指某一個算法，而是某一類算法。判斷的方式就是使用時間復雜度的方法，若算法的下界為A（n），若證明上界也為A（n）的函數，則可以說明該算法是最優算法。

??????以上的過程在本書中，出現的題目多為證明題。證明一個算法小于某個上界或者小于某個下界或上界下界相等。一定要牢記三種標準的定義，來進行證明。

估算算法的運行時間：

??????這是一類計算題，分三大種主要的方法。都是尋找比較核心的操作，計算操作的運行次數作為判斷時間復雜度的標準。該類題的計算方法大多列出連加式，再通過數學方法進行計算。

??????1）計算迭代次數：尋找到各階循環中的基本操作，以他循環的次數作為最終的結果。

??????2） 計算基本運算的頻度：前文提出了迭代的次數與輸入數據的順序有關系，當迭代次數不穩定的時候，可以選擇計算基本運算的頻度來作為衡量時間的標準。以Merge算法為例，當不了解輸入數組A和輸入數組B之間的關系時，可以選擇以賦值操作的頻度作為標準。為2n。

??????3） 使用遞推關系：在某一類基本操作確定后，發現基本操作含有遞歸地定義，那么使用數學方法，找到f(n)和n之間的關系

最壞情況分析和平均情況分析：

?????? 在時間復雜度的分析中，分析最好情況是沒有太多意義的，因為最好的情況不是總發生，不具有代表性。而最壞情況是算法的上界，可以通過分析最壞情況確定最后的界限，并在此之前采取相應的措施。但有的時候最壞情況不是足夠客觀，使用平均情況可以有效的減少最后的結果，但平均情況有特殊的要求：必須了解到各個運算在算法中輸入的各種概率，所以平均情況分析相對復雜。

平攤分析：

??????因為最壞情況分析比較好計算，在大多數情況下使用最壞情況，但如果最壞情況占輸入的比例非常小的時候，全按照最壞情況分析所得出的時間復雜度將會高出一個階，于是為了平衡之間的關系，給出更合理的時間復雜度，會使用平攤分析的方法。平攤分析的具體情況可見博客：link

??????以上是第一章的主要內容，在開頭首先介紹的是算法分析的方法。在后面的章節中會介紹具體的算法，作為基礎應掌握牢固。

偽代碼的使用規范：

要有文字說明的輸入和輸出

每行語句前要有數字表示行數，輸入輸出除外

賦值統一用箭頭表示

對于while要用end while(單列一行)，for要用end for（單列一行）來進行表示

在進行if操作是，在then后面寫if內的操作

總結

以上是生活随笔為你收集整理的算法分析基本概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。