1.2 程序和算法
在現實的世界中，人與人之間的溝通主要是使用語言來進行的。語言是人們創造出來用以表達思想、感情和行為的工具。人類要想和計算機進行交流、要命令計算機來做什么事情同樣也是依賴于語言進行的，但是人和計算機之間的溝通與人和人之間的溝通不一樣，人類要是想讓計算機明白人類想要做什么就必須使用計算機語言（編程語言），然后再借助一定的編譯工具編譯成計算機能夠理解的二進制碼，這樣才能實現人類與計算機之間的溝通，這些命令或語句的相互組合就是計算機程序，本節將主要對計算機程序和算法進行介紹。
1.2.1 程序
程序是為實現特定目標和目的而用計算機編程語言進行組合的具有一定功能的計算機語言序列。這些計算機語言組成的序列從一定程度上講表達的是人的思想，即人要通過計算機來實現什么。程序在計算機中運行時根據計算機環境的不同運行效果會有所改變。例如，同樣一段代碼實現的功能也相同，但是放到不同的計算機上運行的結果雖然一致，但是運行的時間和速度卻存在差別。同樣，即使這段程序在同一臺計算機上運行時也會因為計算機此時的運行效率的不同而使運行速率有所變化，但是不要擔心，因為這些現象都是正常的。
計算機程序是用計算機語言來描述的一系列的功能和動作，它實現了開發人員的思想以及要求計算機代替人類要做的事。開發人員在編寫計算機程序的時候會因為自身對程序的理解而產生各種各樣的區別，編寫出來的程序也存在著各種各樣的優缺點，因此在實際的學習過程中，懂得了C++中的語法并能夠利用C++進行簡單代碼的開發是遠遠不夠的，它與能夠熟練使用C++中的各種功能進行各種簡單或復雜軟件的開發還存在著很大的差距。學習并使用計算機語言，用它來實現人類想要做的事，并保證它能夠在計算機環境下穩定、可靠、高效執行，就要會用計算機程序設計的方法來將計算機語言組成特定的功能序列。學習計算機程序和學習漢語、英語等其他語言一樣，要靠平時的積累和練習，只能多讀、多練才能更好地理解和運用語言，才能夠編寫出穩定、高效、健壯的計算機程序。同樣，在學習的過程中要養成良好的編程習慣，如規范代碼格式、添加代碼注釋等。
開發人員編寫的程序要符合計算機語言的要求規范，因為計算機在運行程序時是按照一定的規范來操作的，只有遵守了計算機語言的開發規范才能保證編寫的程序能夠順利運行。因此，開發人員在編寫程序的時候一定要按照計算機語言的規范來進行編寫，C++程序員也是一樣，必須遵守C++語言的編寫規范，編譯器才能編譯通過，計算機才能順利執行。
1.2.2 算法
許多計算機書中都提到算法是程序的靈魂，算法的設計和開發工作在程序的編寫過程中占據著重要的位置。所謂算法就是為解決一系列問題而編寫設計的一系列程序語句，是程序語句按照一定的功能用途相互組合的結果。通常一個完整的算法都含有零個或多個輸入，然后程序內部對輸入數據進行處理和計算，在經過有限的時間后得到一個正確的結果。如果一個算法存在缺陷，則得不到相應正確的結果。一個完整、正確的算法通常具有以下幾個特征。
? 有窮性：算法在進行了有限次的計算與運行之后必須結束，不能夠在程序中無限循環。
? 確定性：每一個算法中的每一個步驟都是確定、清楚的，在算法中都有確定的意義，不是模糊的。
? 有零個或多個輸入：算法的輸入可以對算法的初始狀態進行初始化，但也可以不對算法的初始狀態進行初始化，即初始化時輸入個數為0。
? 有一個或多個輸出：一個算法必須有一個輸出，也可以有多個輸出。如果一個算法沒有任何輸出，那么這個算法是完全沒有意義的。
? 有效性：算法在經過有限次的運行之后會得到一個正確的、確定的結果。算法的每一個步驟必須有效并且能夠精確地運行。
每一個算法都有一個衡量其效率的標準，算法的復雜度可以分為時間復雜度和空間復雜度。算法的時間復雜度是指算法運行時需要消耗的時間資源。一般來說，計算機算法是問題規模n的函數f(n)，算法的時間復雜度也因此記做T(n)=O(f(n))。
因此，在計算機算法中問題的規模越大，算法運行時消耗的計算機資源也就越多，算法運行的時間也就越長。下面來詳細介紹一下算法時間復雜度的計算方法。
【實例1-1】for循環的時間復雜度。
#include<iostream> //頭文件
using namespace std; //標準命名空間
#define N 10 //定義一個宏
//主函數入口
int main()
{
int i ;
int j ;
int k ;
int sum = 0 ;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
for(k=0;k<N;k++)
{
sum = sum + 1;
}
}
}
}
上面代碼段的功能是累加1，并將累加結果保存到sum變量中，直到循環結束位置。上面的sum = sum + 1語句被執行了1000次，因此算法作用的時間復雜度為N×N×N。記作：
T(n)=O(n^3)
如果算法不一樣，最終可能產生的時間復雜度也不一致。例如，若算法中語句執行次數為一個常數，則時間復雜度為O(1)，另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1的頻度不同，但時間復雜度相同，都為O(n^2)。
按數量級遞增排列，常見的時間復雜度有：常數階O(1)、對數階O(log2n)、線性階O(n)、線性對數階O(nlog2n)、平方階O(n^2)、立方階O(n^3)，...，k次方階O(nk)，指數階O(2n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，算法的執行效率不斷降低。
空間復雜度是指算法在計算機內執行時所需要的存儲空間的大小，空間復雜度與時間復雜度類似，記作S(n)=O(f(n))。
算法的空間復雜度通常由以下三個方面給出。
? 算法本身的長度：算法本身存在著一定的長度，因此算法自身的存儲空間與算法的自身大小成正比例關系，算法越長，占用的存儲空間越多，因此在實際的編寫過程中要盡量編寫出程序較短的算法。
? 算法的輸入與輸出：算法的輸入與輸出是由算法解決的問題來決定的，算法開始時需要傳入的參數越多占用的空間也就越多，反之占用的空間也就越少。
? 算法運行時所占用的臨時空間的大小：算法運行時所占用的臨時空間的大小隨著算法的不同而不同，有的算法在運行過程中占用的臨時空間的大小是固定不變的，也不隨問題規模的大小改變而改變，這種算法就節省了算法的空間復雜度，有的算法在運行過程中所占用的臨時存儲空間是不斷改變的，并隨著問題規模的大小而變化。問題規模越大，占用的存儲空間也就越多。
在分析一個算法的空間復雜度時要從各個方面進行考慮。例如，在遞歸算法中，算法自身的長度可能比較短，自身占用的存儲空間比較小，但是運行時所占用的臨時存儲空間可能會隨著遞歸的運行而不斷增加。在非遞歸算法中，算法自身的長度可能會比較長，算法自身占用的存儲空間比較大，但是在運行時，占用的臨時存儲空間可能會比較小。
在實際的算法設計和開發過程中，對算法的時間復雜度和空間復雜度要綜合進行考慮，不能只偏向一個方面而忽略了整體的效率。對于一個算法，其時間復雜度和空間復雜度往往是相互影響的。時間復雜度滿足要求時，空間復雜度的性能可能變得很差，即可能會占用較多的存儲空間；反之，當空間復雜度獲得良好的效果時，時間復雜度的性能可能會變得很差，即可能會占用較長的運行時間。另外，算法的所有性能之間都存在著或多或少的相互影響。因此，當設計一個算法（特別是大型算法）時，要綜合考慮算法的各項性能、算法的使用頻率、算法處理的數據量的大小、算法描述語言的特性、算法運行的機器系統環境等各方面因素，才能夠設計出比較好的算法。