Array Indexing

Array Indexing

「索引」可說是電腦的奇技!一個元素存放到陣列之後,不論是在陣列的哪個地方,只要利用索引值(index),就能在一瞬間找到元素。

大多數的演算法都運用了「索引」的技巧,讓程式執行速度更快。

以下介紹索引的幾種運用方式。是我自己歸類整理的,並不是標準。

一、定位

概念為:將物件放入陣列中,array[位置] = 物件。

當元素很多時,我們可以放到陣列裡。我們只要記錄索引值,依舊可以常數時間得到元素。

範例:求最大值。將元素連續地放入陣列,若想紀錄一元素,僅需一索引值。

範例:求子字串。將元素連續地放入陣列,若想紀錄一區間,僅需頭尾的索引值。

範例:連續數字和。將元素連續地放入陣列,利用問題本身的數學性質以及索引值,快速得到答案。

範例:求中位數。將元素依照大小順序並連續地放入陣列,利用索引值得到位於中間的元素。

範例:二分搜尋法(Binary Search)。將元素依照大小順序並連續地放入陣列,然後夾擠索引值。如果使用的是鏈接串列,因為元素們都沒有索引值,就無法使用二分搜尋法。

範例:二元樹(Binary Tree)。元素的索引值對應到樹的結構,是一種特殊的定位。

範例:堆疊(stack)、佇列(queue)。元素連續地放入陣列,然後以改變索引值的方式,來動態增減堆疊及佇列的元素。

二、歸類並標記

概念為:物件直接作為陣列的索引值,array[物件] = 物件的屬性。

範例:正整數集合。物件是:正整數,物件的屬性是:是否在集合裡頭出現。

範例:統計英文字母出現次數。物件是英文字母,物件的屬性是英文字母的出現次數。

範例:計數排序法(Counting Sort)。索引值的大小順序,剛好也是元素的大小順序,故可用於排序。

範例:雜湊表(hash table)。元素的索引值由特殊方法決定,是一種特殊的歸類。

三、轉換

概念為:array[物件] = 另一個物件。類似函數的概念。

範例:取代(Substitution)、移位(Transposition)。取代和移位是密碼學的基礎概念。取代是文字的轉換,移位則是位置的轉換。

範例:page table。作業系統的機制,可將虛擬位址轉換成實體位址,是位址的轉換。

附錄:定址的時間複雜度

當索引值大小為N時,有人認為定址的時間複雜度是O(log2N),也有人認為是O(1)。這兩種說法都是有其依據的。

以數學的觀點來看:N共有log2N個位元,用二元樹的概念,依照各個位元的數值是0或是1進行分支,分支到底後就完成定址了。所以定址的時間複雜度是O(log2N)。

以電路的觀點來看:一顆中央處理器可以平行處理32位元(現在已有64位元),只要是介於0到2^32-1的索引值,都可以在1單位時間完成定址,而不必用32單位時間來完成定址。所以定址的時間複雜度是O(1)。

討論演算法的時間複雜度時,我們傾向假設定址的時間複雜度是O(1)。

附錄:定址的範圍

方才提到一顆中央處理器可以平行處理32位元,理論上可以定址到2^32以內的位址。一個位址一般擁有1byte的記憶體大小,所以我們利用定址方式,可以運用的記憶體就有2^32 * 1byte = 4GB 這麼多。

但是作業系統會保留一些位址、預留一些記憶體空間以維持系統運作,所以使用者實際可以運用的記憶體其實不到4GB。

當記憶體沒有插到4GB的時候,作業系統利用一種叫做virtual memory的技術,以硬碟空間補足記憶體不足4GB的部份。

位址是連續不斷的,我們寫程式也都直接假設位址對應到的記憶體空間是連續不斷的,然而實際上並不是連續的。作業系統運用一種叫做paging的技術,藉由page table,讓記憶體看起來是連續的。