一.計算:

一個算法的幾個要素:

輸入，輸出，正確性，有窮性，可行性，健壯性。

程序！==? 算法

什么是好算法?

正確，健壯，可讀(結(jié)構(gòu)化，命名，注釋)都很重要，但并不是好算法。

效率(速度快，存儲空間少)(時間成本+空間成本)

(Algorithms+data struct)*efficiency=computation

二.問題規(guī)模:

問題實例的規(guī)模，往往是計算成本的主要因素。

規(guī)模越近，計算成本也越近。

2.1 最壞情況

2.2 理想模型

同一算法，如何評價優(yōu)劣？

2.3 圖靈機模型

q狀態(tài)

c值

d新值

l/r左右

p新狀態(tài)

h停機

2.4 圖靈機實例

圖靈機模型

2.5 RAM模型

三 大O記號

3.1長遠，主流

足夠大，增長趨勢

3.2對數(shù)，高效解O(log(n))

常數(shù)，對數(shù)(常底數(shù)無所謂，常數(shù)次冪無所謂)

3.3多項式，有效解O(n∧2)

3.4指數(shù)，難解O(2∧n)