19/9/2024

分析某个算法的三部曲：

是不是正确的（Is it correct?）
花了多长时间（How much time does it take, as a function of n?）
能不能更好（Can we do better?）

斐波那契算法（Fibonacci Algorithms）

经典的斐波那契数列：

0，1，1，3，5，8，13，21，34

传统算法:
FIBO1(n)
a nature number n;
if n = 0 then return(0);
if n = 1 then return(1);
return(FIBO1(n − 1)+FIBO1(n − 2));

分析：

空间换时间算法：
FIBO2(n)
a nature number n;
if n = 0 then return(0);
create an array f[0 . . . n];
f[0] = 0; f[1] = 1;
for i = 2 to n do
f[i] = f[i − 1] + f[i − 2];
end
return(f[n]);

分析：

按照常理乍一看，应该是O(n),但是细细看：当n变大时，数字变大，计算加法等步骤就不再是常数了。

两个n位数字相加所需的时间大致与n成正比，所以大概与n^2成正比。

Big-O Notation（大O）

理论：Upper bounds上界，说直白点就是看最高的复杂度（就是增长的最快速的一项，可以更大

等于性：O(g(n))是一类函数的集合，但是为了方便写成f(n)=O(g(n)).

性质：

Reflexivity. f=O(f)
Constants: If f is O(g) and c > 0, then c f is O(g). [正常数倍的扩大缩小不会影响O]
Products: if f1 is O(g1) and f2 is O(g2) ,then f1f2 is O(g1g2) [乘法可以适用]

证明：
Sums: If f1 is O(g1) and f2 is O(g2) ,then f1+f2 is O*(max*{g1, g2}) [加法取最大]
Transitivity: If f is O(g) and g is O(h), then f is O(h). [O里能传递就完了]