详细的算法介绍不再介绍,网上到处都是。
未优化的算法:
优化后的算法:
推导过程:
优化前推导:
T(1)=O(1);
T(2)=4O(1)+O(2);
T(4)=16O(1)+4O(2)+O(4);
T(8)=64O(1)+16O(2)+4O(4)+O(8);
.....
T(n)=n²O(1)+n²/4O(2)+n²/16O(4)+.....+O(n);
根据性质f=O(f) ① 得:
T(n)=O(n²)*O(1)+O(n²/4)*O(2)+O(n²/16)*O(4)+.....+O(n);
根据性质O(f)*O(g)=O(fg) ② 得：
T(n)=O(n²)+O(n²/2)+O(n²/4)+....+O(n);
根据性质O(f)+O(g)=O(max(f,g)) ③ 又因为n>=1,因此n²>n²/2>n²/4>.....>n;
因此T(n)=O(n²)。
（性质均来自王晓东《计算机算法设计与分析》P3）
同理可以推得优化后的T(n)=O(n^log(3/2)).