哪怕只寫過幾行代碼的人都會發現，編程基本上就是在跟數據打交道。計算機程序總是在接收數據、操作數據或返回數據。不管是求兩數之和的小程序，還是管理公司的企業級軟件，都運行在數據之上。

數據是一個廣義的術語，可以指代各種類型的信息，包括最基本的數字和字符串。在經典的“Hello World!”這個簡單程序中，字符串"Hello World!"就是一條數據。事實上，無論是多么復雜的數據，我們都可以將其拆成一堆數字和字符串來看待。

數據結構則是指數據的組織形式。看看以下代碼。

x = "Hello!"y = "How are you"z = "today?"
print x + y + z

這個非常簡單的程序把3 條數據串成了一句連貫的話。如果要描述該程序中的數據結構，我們會說，這里有3 個獨立的變量，分別引用著3 個獨立的字符串。

在這里，你將學到，數據結構不只是用于組織數據，它還極大地影響著代碼的運行速度。因為數據結構不同，程序的運行速度可能相差多個數量級。如果你寫的程序要處理大量的數據，或者要讓數千人同時使用，那么你采用何種數據結構，將決定它是能夠運行，還是會因為不堪重負而崩潰。

一旦對各種數據結構有了深刻的理解，并明白它們對程序性能方面的影響，你就能寫出快速而優雅的代碼，從而使軟件運行得快速且流暢。當然，你的編程技能也會更上一層樓。

接下來我們將會分析兩種比較相似的數據結構：數組和集合。它們從表面上看好像差不多，但通過即將介紹的分析工具，你將會觀察到它們在性能上的差異。

基礎數據結構：數組

數組是計算機科學中最基本的數據結構之一。如果你用過數組，那么應該知道它就是一個含有數據的列表。它有多種用途，適用于各種場景，下面就舉個簡單的例子。

一個允許用戶創建和使用購物清單的食雜店應用軟件，其源代碼可能會包含以下的片段。

array = ["apples", "bananas", "cucumbers", "dates", "elderberries"]

這就是一個數組，它剛好包含5 個字符串，每個代表我會從超市買的食物。

此外，我們會用一些名為索引的數字來標識每項數據在數組中的位置。

在大多數的編程語言中，索引是從0 算起的，因此在這個例子中，"apples"的索引為0，"elderberries"的索引為4，如下所示。

若想了解某個數據結構（例如數組）的性能，得分析程序怎樣操作這一數據結構。

一般數據結構都有以下4 種操作（或者說用法）。

• 讀取：查看數據結構中某一位置上的數據。對于數組來說，這意味著查看某個索引所指的數據值。例如，查看索引2 上有什么食品，就是一種讀取。
• 查找：從數據結構中找出某個數據值的所在。對于數組來說，這意味著檢查其是否包含某個值，如果包含，那么還得給出其索引。例如，檢查"dates"是否存在于食品清單之中，給出其對應的索引，就是一種查找。
• 插入：給數據結構增加一個數據值。對于數組來說，這意味著多加一個格子并填入一個值。例如，往購物清單中多加一項"figs"，就是一種插入。
• 刪除：從數據結構中移走一個數據值。對于數組來說，這意味著把數組中的某個數據項移走。例如，把購物清單中的"bananas"移走，就是一種刪除。

接下來我們將會研究這些操作在數組上的運行速度。同時，我們也將學到第一個重要理論：操作的速度，并不按時間計算，而是按步數計算。

為什么呢？

因為，你不可能很絕對地說，某項操作要花5 秒。它在某臺機器上要跑5 秒，但換到一臺舊一點的機器，可能就要多于5 秒，而換到一臺未來的超級計算機，運行時間又將顯著縮短。所以，受硬件影響的計時方法，非常不可靠。

然而，若按步數來算，則確切得多。如果A 操作要5 步，B 操作要500 步，那么我們可以很肯定地說，無論是在什么樣的硬件上對比，A 都快過B。因此，衡量步數是分析速度的關鍵。

此外，操作的速度，也常被稱為時間復雜度。本文中，我們提到速度、時間復雜度、效率、性能，它們其實指的都是步數。

事不宜遲，我們現在就來探索上述4 種操作方式在數組上要花多少步。

1. 讀取

首先看看讀取，即查看數組中某個索引所指的數據值。

這只要一步就夠了，因為計算機本身就有跳到任一索引位置的能力。在["apples","bananas", "cucumbers", "dates", "elderberries"]的例子中，如果要查看索引2 的值，那么計算機就會直接跳到索引2，并告訴你那里有"cucumbers"。

計算機為什么能一步到位呢？原因如下。

計算機的內存可以被看成一堆格子。下圖是一片網格，其中有些格子有數據，有些則是空白。

當程序聲明一個數組時，它會先劃分出一些連續的空格子以備使用。換句話說，如果你想創建一個包含5 個元素的數組，計算機就會找出5 個排成一行的空格子，將其當成數組。

內存中的每個格子都有各自的地址，就像街道地址，例如大街123 號。不過內存地址就只用一個普通的數字來表示。而且，每個格子的內存地址都比前一個大1，如下圖所示。

購物清單數組的索引和內存地址，如下圖所示。

計算機之所以在讀取數組中某個索引所指的值時，能直接跳到那個位置上，是因為它具備以下條件。

(1) 計算機可以一步就跳到任意一個內存地址上。（就好比，要是你知道大街123 號在哪兒，那么就可以直奔過去。）

(2) 數組本身會記有第一個格子的內存地址，因此，計算機知道這個數組的開頭在哪里。

(3) 數組的索引從0 算起。

回到剛才的例子，當我們叫計算機讀取索引3 的值時，它會做以下演算。

(1) 該數組的索引從0 算起，其開頭的內存地址為1010。

(2) 索引3 在索引0 后的第3 個格子上。

(3) 于是索引3 的內存地址為1013，因為1010 + 3 = 1013。

當計算機一步跳到1013 時，我們就能獲取到"dates"這個值了。

所以，數組的讀取是一種非常高效的操作，因為它只要一步就好。一步自然也是最快的速度。這種一步讀取任意索引的能力，也是數組好用的原因之一。

如果我們問的不是“索引3 有什么值”，而是“"dates"在不在數組里”，那么這就需要進行查找操作了。下面我們就來看看。

2.查找

如前所述，對于數組來說，查找就是檢查它是否包含某個值，如果包含，還得給出其索引。

那么，我們就試試在數組中查找"dates"要用多少步。

對于我們人來說，可以一眼就看到這個購物清單上的"dates"，并數出它的索引為3。但是，計算機并沒有眼睛，它只能一步一步地檢查整個數組。

想要查找數組中是否存在某個值，計算機會先從索引0 開始，檢查其值，如果不匹配，則繼續下一個索引，以此類推，直至找到為止。

我們用以下圖來演示計算機如何從購物清單中查找"dates"。

首先，計算機檢查索引0。

因為索引0 的值是"apples"，并非我們所要的"dates"，所以計算機跳到下一個索引上。

索引1 也不是"dates"，于是計算機再跳到索引2。

但索引2 的值仍不匹配，計算機只好再跳到下一格。

啊，真是千辛萬苦，我們找到"dates"了，它就在索引3 那里。自此，計算機不用再往后跳了，因為結果已經得到。

在這個例子中，因為我們檢查了4 個格子才找到想要的值，所以這次操作總計是4 步。

這種逐個格子去檢查的做法，就是最基本的查找方法——線性查找。當然還可以學習其他查找方法，但在那之前，我們再思考一下，在數組上進行線性查找最多要多少步呢？

如果我們要找的值剛好在數組的最后一個格子里（如本例的elderberries），那么計算機從頭到尾檢查每個格子，會在最后才找到。同樣，如果我們要找的值并不存在于數組中，那么計算機也還是得查遍每個格子，才能確定這個值不在數組中。

于是，一個5 格的數組，其線性查找的步數最大值是5，而對于一個500 格的數組，則是500。

以此類推，一個N 格的數組，其線性查找的最多步數是N（N 可以是任何自然數）。

可見，無論是多長的數組，查找都比讀取要慢，因為讀取永遠都只需要一步，而查找卻可能需要多步。

接下來，我們再研究一下插入，準確地說，是插入一個新值到數組之中。