算法分析--幂测试

最近看《算法分析与设计》，里面提到了一个用实验来估计算法的时间复杂度的方法：幂测试。具体来说就是假设算法的时间函数是 f(n)，然后将数对(n,f(n))映射成(log(n),log(f(n)))。这样如果原来f(n)=a * n^c，也就是时间函数是个幂函数，则可得到 log(f(n)) = log(a * n^c) = log(a) + c * log(n)，是一个线性函数。
基于上面的理论，我们可以通过试验数据来绘制曲线：x=log(n),y=(log(f(n)))。如果曲线收敛到一个常数，则f(n)是个亚线性函数；如果是条直线，则f(n)是个幂函数；如果曲线急剧增长，则f(n)是超多项式的，例如指数函数等。

下面是一个简单的html5代码，用来绘制一个函数的幂测试曲线。现实中可以将试验数据拼装成json数据，然后由下面的代码绘制。

 1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
 2 <html xmlns="http://www.w3.org/1999/xhtml">
 3 <head>
 4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
 5 <title>幂测试</title>
 6 <script src="http://code.jquery.com/jquery-1.10.1.min.js"></script>
 7 </head>
 8 
 9 <body>
10     <canvas id='g' width="470px" height="350px" style="border:2px; background:black;">
11     </canvas>
12     <textarea id="log" style="470px;height:350px;"></textarea>
13 </body>
14 <script type="text/javascript">
15 var consts = {
16     width : 450,
17     height : 330,
18     scaleX : 20.0,
19     scaleY : 10.0,
20     maxN : 10000,
21     step : 10,
22     pad : 5
23 };
24 
25 function log(n) {
26     return Math.log(n) / Math.log(2);
27 };
28 
29 //函数
30 function f(n) {
31     //return 12 * n; //线性
32     //return 6 * n * log(n);
33     //return n * n * n; //3次函数
34     return Math.pow(2, n);//指数函数
35 };
36 
37 var g = $('#g')[0].getContext('2d');
38 g.strokeStyle = '#BBFFFF';
39 g.lineWidth = 2;
40 
41 var pad = consts.pad;
42 var pad2 = consts.pad * 2;
43 //绘制纵坐标
44 g.moveTo(pad2,pad2 + consts.height);
45 g.lineTo(pad2,consts.pad);
46 g.lineTo(pad2-2,pad+5);
47 g.moveTo(pad2,pad);
48 g.lineTo(pad2+2,pad+5);
49 
50 //绘制横坐标
51 g.moveTo(pad,pad + consts.height);
52 g.lineTo(pad2 + consts.width, pad + consts.height);
53 g.lineTo(pad2 + consts.width-5, pad + consts.height-2);
54 g.moveTo(pad2 + consts.width, pad + consts.height);
55 g.lineTo(pad2 + consts.width-5, pad + consts.height+2);
56 
57 //绘制函数的log图 x->log(n), y->log(f(n))
58 for(var i = 2; i < consts.maxN; i += consts.step) {
59     var x = log(i);
60     var y = log(f(i));
61     var px = pad2 + x * consts.scaleX;
62     var py = pad + consts.height - y * consts.scaleY;
63     if(i == 2)
64         g.moveTo(px,py);
65     else
66         g.lineTo(px,py);
67         
68     //$('#log').append(i + ':' + Math.round(x*100)/100.0 + ',' + Math.round(y*100)/100.0 + '
');
69 }
70 
71 g.stroke();
72 </script>
73 </html>