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
5
new_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)組成的字串

概念

可以把兩份文件的共通性以兩份文件所包含字詞的共通性來思考。

主要步驟

  1. 將文件分割為words
  2. 算出每個word的出現頻率
  3. 算兩個文件的word陣列的內積（即角度）

課程連結

MIT 6.006 Introduction to ALgorithms, Fall 2011