这是在学习浙大陈越老师数据结构课程的时候做的笔记，第一次写博客，希望坚持下去！刚开始可能笔记记的比较笨，以后慢慢就精炼一点。看起来陈老师是用c写的，我想用java来写，但是java语法还没怎么学，如果有人看到的话，尤其是看到哪里有问题有比较笨比的地方的话，希望可以帮我指正，感谢！！！

1.1 关于数据组织

解决问题方法的效率，跟数据的组织方式有关。

1.2 关于空间使用

eg: 实现函数PrintN，传入正整数N，顺序打印1到N

方法：1.循环 2.递归

　　　循环需要一个虚拟变量，递归不需要；但是当输入为100,000时，递归方法罢工了...

           递归代码简洁，但是对空间占用可能比较恐怖。

解决问题方法的效率，跟空间的利用效率有关

1.3 关于算法效率

eg: 写程序计算给定多项式在给定点x处的值  f(x) = a₀ + a₁x +...+ a_n-1x^n-1 + a_nxⁿ 

方法：1.直接逐项计算  2.秦九韶算法

package Chapter1;

public class Polynomial {
    // Loop
    public static double loopmethod(double[] a, double x){
        double p = a[0];
        for(int i = 1; i<= a.length-1; i++){
            p += a[i]*Math.pow(x,i);
        }
        return p;
    }
    // 秦九韶算法
    public static double Qmethod(double[] a, double x){
        int n = a.length-1;  // n is the degree of the polynomial
        double p = a[n];
        for(int i = n; i>0; i--){
            p = a[i-1] + x*p;
        }
        return p;
    }

    public static void main(String[] args) {

        int MaxK = 100000000;  // 方法重复调用次数
        double[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

        long startTime = System.currentTimeMillis();
        for (int i = 1; i <= MaxK; i++) {
            loopmethod(a, 1.1);
        }
        long endTime = System.currentTimeMillis();
        double usedTime = (endTime - startTime)/1000;
        System.out.print("\nLoop method cost ");
        System.out.print(usedTime);
        System.out.print("\nThe result of loop is");
        System.out.print(loopmethod(a, 1.1));

        long startTime2 = System.currentTimeMillis();
        for (int i = 1; i <= MaxK; i++) {
            Qmethod(a, 1.1);
        }
        long endTime2 = System.currentTimeMillis();
        double usedTime2 = (endTime2 - startTime2)/1000;
        System.out.print("\nQJS method cost ");
        System.out.print(usedTime2);
        System.out.print("\nThe result of QJS is");
        System.out.print(Qmethod(a, 1.1));
    }
}


/*
1. 原本是在方法内部计算usedtime但是计算出两个方法运行时间是0，因为程序太快惹
   解决方案：可以让被测函数重复运行多次，使得测出的总的时钟打点间隔充分长，最后计算平均每次运行时间。
           哎再改一下...把测时步骤改到main里然后再加循环多运行几次，运行了1e8次，秦九韶算法果然快很多。
           计时可以用currentTimeMillis()或nanoTime()
2. 本来写的int MaxK = 1e8,结果报错 需要的数据类型为int 提供的数据类型为double;
   原来是浮点型数字才能用科学计数法表示，学到了
 */

计算机中乘法时间成本>加法

解决问题方法的效率，跟算法的巧妙程度有关。

chapter1未完待续...