算法分析设计-关于算法

1. 什么是算法？

算法是解决某个问题的确定性指令序列，满足性质：

输入：有外部提供的量作为算法的输入。
输出：算法产生至少一个量作为输出。
确定性：组成算法的每条指令是清晰，无歧义的。
有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

算法的本质：是解决问题的方法。

算法的优势：（1）把麻烦的事交给计算机做（2）可以解决一类问题

算法的核心任务：设计合理的算法。

2. 如何表示算法？

自然语言
流程图（清晰直观）
伪代码
计算机语言

3. 如何评价算法？

4. 求解斐波那锲数列

//Fibonacci
/**
 * 求解斐波那契数
 */
public class Fibonacci {
    /**
     * 递归法
     * @param n
     * @return
     */
    public static long getByRecursion(long n){
        if(n == 1 || n == 2){
            return 1;
        }

        return getByRecursion(n-1) + getByRecursion(n-2);
    }

    /**
     * 迭代法
     * @param n
     * @return
     */
    public static long getByIteration(long n){
        long a = 1;
        long b = 1;

        if(n == 1 || n == 2){
            return 1;
        }

        long temp = 0;
        for(int i = 3; i <= n; i ++) {
            temp = a + b;

            a = b;
            b = temp;
        }

        return temp;
    }
}

//FibonacciTest
package swu.xl.algorithm.code_02_25.experiment_1;

import java.io.FileWriter;
import java.io.IOException;

public class FibonacciTest {
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        int startNumber = 10;			// the start number as the parameter n
        int trialNumber = 41;			// the number of trials

        long[][] recordData = new long[trialNumber][5];
        // records for each trial, including the parameter n, and the time used for two methods (recursion and iteration).

        for(int i=0;i<trialNumber;i++) {	// One loop for each trial.
            long n = startNumber + i;

            long startTimeRecursion = System.currentTimeMillis();	//start time
            long fib_recursion = Fibonacci.getByRecursion(n); 	//get Fibonacci by recursion
            long endTimeRecursion = System.currentTimeMillis();  	//end time

            long startTimeIteration = System.currentTimeMillis();	//start time
            long fib_iteration = Fibonacci.getByIteration(n); 	//get Fibonacci by recursion
            long endTimeIteration = System.currentTimeMillis();  	//end time

            recordData[i][0] = n;
            recordData[i][1] = fib_recursion;
            recordData[i][2] = fib_iteration;
            recordData[i][3] = endTimeRecursion - startTimeRecursion;
            recordData[i][4] = endTimeIteration - startTimeIteration;

            System.out.println("Parameter(n): " + recordData[i][0] + "; recursion result: " + recordData[i][1] + "; iteration result: "
                    + recordData[i][2] + "; recursion time: " + recordData[i][3] + "; iteration time: "
                    + recordData[i][4] + ".");		//print the parameter n , the results of two methods, and the running times of two methods
        }

        FileWriter csvWriter = new FileWriter("data.csv");
        for(int i=0;i<trialNumber;i++) {
            csvWriter.append(" " + recordData[i][0] + "," + recordData[i][3] + "\n");
        }
        csvWriter.close();
        System.out.println("Please find the data file at " + System.getProperty("user.dir"));
    }

}

5. 求解最大公约数

//GCD
/**
 * 求解最大公因数
 */
public class GCD {
    /**
     * 暴力枚举法
     * @param a
     * @param b
     * @return
     */
    public static int getByBruteForce(int a, int b){
        int result = 0;

        for (int i = Math.min(a, b); i > 0; i--) {
            if (a % i == 0 && b % i == 0){
                result = i;
                break;
            }
        }

        return result;
    }

    /**
     * 欧几里得法
     * @param a
     * @param b
     * @return
     */
    public static int getByEuclid(int a, int b){
        while(a != 0 && b != 0){
            if(a > b){
                a = a % b;
            }else{
                b = b % a;
            }
        }

        return a+b;
    }

    /**
     * 测试函数
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(getByEuclid(2,12));
        System.out.println(getByBruteForce(2,12));
    }
}

//GCDTest
public class GCDTest {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int startNum = 100000000;
        int increment = 100000000;
        int runTime = 20;

        for(int i=0; i<runTime; i++) {
            int b = startNum + i*increment;
            int a = new java.util.Random().nextInt(b);

            long startTimeEuclid = System.currentTimeMillis();
            int gcd_euclid = GCD.getByEuclid(a,b);
            long endTimeEuclid = System.currentTimeMillis();
            long time_euclid = endTimeEuclid - startTimeEuclid;

            long startTimeBrute = System.currentTimeMillis();
            int gcd_brute = GCD.getByBruteForce(a,b);
            long endTimeBrute = System.currentTimeMillis();
            long time_brute = endTimeBrute - startTimeBrute;

            System.out.println("Max of the input (b): " + b + "; euclid result: "
                    + gcd_euclid + "; brute result: " + gcd_brute + "; euclid time: "
                    + time_euclid + "; brute time: " + time_brute + ".");
        }
    }
}