算法第四版 1.4.3

清疚 2022-03-17 07:16 255阅读 0赞

# 题目 #

修改DoublingTest,使用StdDraw产生类似于正文中的标准图像和对数图形,根据需要调整比例使图像总能够充满窗口的大部分区域

# 分析 #

对库函数StdDraw的理解和运用,  
根据图像分析增长的数量级  
x坐标是规模n取对数  
y坐标是耗时time取对数

# java代码 #

import edu.princeton.cs.algs4.StdDraw;
    import edu.princeton.cs.algs4.StdRandom;
    import edu.princeton.cs.algs4.ThreeSum;
    
    /**
     * @description: ${description}
     * @create: 2019-02-20
     **/
    public class DoublingTest {
        public static double timeTrial(int n){
            int max=1000000;
            int[] a = new int[n];
            for(int i=0;i<n;i++){
                a[i]= StdRandom.uniform(-max,max);
            }
            StopWatch timer=new StopWatch();
            int cnt = ThreeSum.count(a);
            return timer.elapsedTime();
        }
    
        public static void main(String[] args) {
            for(int n=250;true;n=n+n){
                double time = timeTrial(n);
                StdDraw.setXscale(-1,20.0);
                StdDraw.setYscale(-10,10.0);
                StdDraw.setPenRadius(0.006);
                double x=Math.log(n);
                double y=Math.log(time);
                StdDraw.point(x,y);
                System.out.println(n+"\t"+time);
            }
        }
    }

# 结果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]  
前两个数250和500不是很准  
后面四个数字1000 2000 4000 8000还是挺准的  
根据数据计算斜率  
double k1=(Math.log(12.152)-Math.log(1.604))/(Math.log(4000)-Math.log(2000));  
double k2=(Math.log(92.993)-Math.log(12.152))/(Math.log(8000)-Math.log(4000));  
k1=2.92 k2=2.93  
接近3.说明是3-sum立方级别的关系

# 心得 #

写的比较粗糙

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220317/94d3bbdd52b5495b9ae3fe8e361cfa8b.png