数据结构(3) -- 关于算法效率

深藏阁楼爱情的钟 2023-07-04 03:27 21阅读 0赞

### 关于算法效率 ###

*  例子:

# 例子: #

![在这里插入图片描述][20200207161618917.png]  
有2种写法:

*  最容易想到的方法:

//方式1： 比较low的写法
        private static double getF1(int n, double[] a, double x) { 
            int i;
            double p = a[0];
            for (i = 1; i <= n; i++) { 
                p += (a[i] * Math.pow(x, i));
            }
            return p;
        }

*  秦九韶算法  
    ![在这里插入图片描述][20200207183858811.png]

//方式2： f (x) = a0 + x(a1 + x(…(an-1 + x(an))…))
        //秦九韶算法 结合律 从里往外算
        private static double getF2(int n, double[] a, double x) { 
            int i ;
            double p = a[n];
            for (i = n; i > 0; i--) { 
                p = a[i - 1] + x * p;
            }
            return p;
        }

测试:假设 n=9，x=1.1，a为10个数字的数组，存储的是0-10:

public static void main(String[] args) { 
            int n = 9;
            double x = 1.1;
            double[] a = new double[10];
            for (int i = 0; i <= n; i++) { 
                a[i] = (double) i;
            }
    
            long startTime = System.currentTimeMillis();
            System.out.println(startTime);
            double f1 = 0;
            for (int j=0;j<100000;j++){ 
                 f1 = getF1(n, a, x);
            }
    
            System.out.println(f1);
            long endTime = System.currentTimeMillis();
            System.out.println(startTime);
            System.out.println(endTime - startTime);
    
            System.out.println("------");
    
            long startTime2 = System.currentTimeMillis();
            System.out.println("startTime2==" + startTime2);
            double f2 = 0;
            for (int j=0;j<100000;j++){ 
                 f2 = getF2(n, a, x);
            }
            System.out.println(f2);
            long endTime2 = System.currentTimeMillis();
            System.out.println(endTime2);
            System.out.println(endTime2 - startTime2);
        }

> 因为我的是固态硬盘，执行一遍代码看不出来效果，循环执行100000遍，可以看到时间差别,差了一个数量级:  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70]

--------------------

这个例子说明:  
![在这里插入图片描述][20200207184049101.png]

--------------------

完

[20200207161618917.png]: https://img-blog.csdnimg.cn/20200207161618917.png
[20200207183858811.png]: https://img-blog.csdnimg.cn/20200207183858811.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207183821737.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1,size_16,color_FFFFFF,t_70
[20200207184049101.png]: https://img-blog.csdnimg.cn/20200207184049101.png