Random access Machine
Pointer Machine
Python machine
更現代的Python結合以上兩種模型。
基本情況
List
Python中實作List的方式使用RAM模型，透過a_list[i]取得list中某一索引的元素，所花的時間為常數時間O(1)。
如果以linked list的方式來實作，那麼取出索引i的元素所花的時間即成為線性時間O(n)。
Object
如果一物件有適當數量的元素，那麼取出該物件屬性的執行時間也是常數時間O(1)。
幾個例子
list.append
使用 table doubling 方法（在之後的第九課將提到），使執行時間達到常數時間O(n)。
new_list = list1 + list2
上面的程式碼在底層其實是執行下方的程式碼。1
2
3
4
5new_list = []
for x in list1:
new_list.append(x)
for y in list2:
new_list.append(y)
因此可利用append()方法的執行時間來推導將兩個list相連在一起的執行時間: O(|list1| + |list2|)，即正比於兩個list的元素數量總和。
elm in a_list
線性時間O(n)，從第一個元素依序檢查到最後一個。
len(a_list)
常數時間O(1)，因為Python在底層已經先計算好並儲存每個list的長度。所以呼叫len(a_list)只是去叫出那個被儲存的值。
list.sort()
dict
以hash table實作，因此以dict[key]叫出該對應value的執行時間為常數時間O(n)。
Document distance Problem
目標
有兩份文件，想測量這兩份文件的距離，即這兩份文件的共通性。
應用
- Google index page
- Mirror of Wiki
- 檢查兩份期末報告是否互相抄襲
定義
- 文件:由words組成
- word: 為字元(a-z, A-Z, 0-9)組成的字串
概念
可以把兩份文件的共通性以兩份文件所包含字詞的共通性來思考。
主要步驟
- 將文件分割為words
- 算出每個word的出現頻率
- 算兩個文件的word陣列的內積（即角度）