14天閱讀挑戰賽（認識算法的特性）

14天閱讀挑戰賽

努力是為了不平庸~

算法學習有些時候是枯燥的，這一次，讓我們先人一步，趣學算法！歡迎記錄下你的那些努力時刻（算法學習知識點/算法題解/遇到的算法bug/等等），在分享的同時加深對于算法的了解，同時吸收他人的奇思妙想，一起見證技術er的成長~

目錄

一、什麼是算法

二、算法的複雜性

三、空間複雜度

四、時間複雜度

一、什麼是算法

瑞士著名的科學家Niklaus Wirth教授曾提出：**資料結構+算法=程式**。

資料結構是程式的骨架，算法是程式的靈魂。

二、算法的複雜性

例、寫一個算法，求以下序列之和：

-1，1，-1，1，…，（-1）^n

算法一：

```

int sum(int n)

{

    int sum=0;

    for(int i=1;i<=n;i++)

    sum+=pow(-1,i);//表示(-1)^i

    return sum;

}    

```

算法二：

```

int sum(int n)

{

    int sum=0;

    if(sum%2==0)

    sum=1;

    else

    sum==-1;

    return sum;

}

```

算法是對特定問題求解步驟的一種描述。

算法具有以下特性。

1. 有窮性：算法是由若幹條指令組成的有窮序列，總是在執行若幹次後結束，不可能永不停止。

2. 确定性：每條語句都有确定的含義，無歧義。

3. 可行性：算法在目前環境條件下可以通過有限次運算來實作。

4. 輸入輸出：有零個或多個輸入以及一個或多個輸出。

三、空間複雜度

算法占用的空間大小。

空間複雜度的本意是指算法在運作過程中占用了多少存儲空間。算法占用的存儲空間包括：

1. 輸入輸出資料；

2. 算法本身；

3. 額外需要的輔助空間。

輸入輸出資料占用的空間是必需的，算法本身占用的空間可以通過精簡算法來縮減，但縮減的量是很小的，可以忽略不計。算法在運作時所使用的輔助變量占用的空間（即輔助空間）才是衡量算法空間複雜度的關鍵因素。

四、時間複雜度

算法運作需要的時間。

算法的運作時間主要取決于最高項，小項和常數項忽略不計。

常見的算法時間複雜度有以下幾類。

1. 常數階。

   常數階算法的運作次數是一個常數，如5、20、100。常數階算法的時間複雜度通常用O(1)表示。

2. 多項式階。

   很多算法的時間複雜度是多項式，通常用O(n)、O(n²)、O(n³)等表示。

3. 指數階。

   指數階算法的運作效率極差，程式員往往像躲“惡魔”一樣避開這種算法。指數階算法的時間複雜度通常

   用O(2")、O(n!)、O(n")等表示。

4. 對數階。

   對數階算法的運作效率較高，通常用O(logn)、O(nlogn)等表示。

   指數階增量随着的增加而急劇增加，而對數階增長緩慢。它們之間的關系如下：

   O(1)<O(logn)<O(n)<O(nlogn)O(n²)<O(n³)<O(2")O(n!)<O(n")

   在設計算法時，我們要注意算法複雜度增量的問題，盡量避免爆炸級增量。

本節主要說明了以下問題。

- 将程式執行次數作為時間複雜度衡量标準。

- 時間複雜度通常用漸近上界符号O((n)表示。

- 衡量算法的好壞時通常考查算法的最壞情況。

- 空間複雜度隻計算輔助空間。

- 遞歸算法的空間複雜度需要計算遞歸使用的棧空間。

- 設計算法時要盡量避免爆炸級增量複雜度。