铭记:

一、什么是算法

算法是用于解决特定问题的一系列的执行步骤

• 使用不同的算法，解决同一个问题，效率可能相差非常大
• 斐波那契数列

0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

算法一：使用递归求和

    /**
     * 斐波那契数列（算法一）
     * @param index 下标位置
     * @return index 位置的数值
     * 下标：0、1、2、3、4、5、6、7、  8、 9、.... n
     * 数值：0、1、1、2、3、5、8、13、21、34
     */
    private static Integer fibonacci1(Integer index) {
        if (index < 2) {
            return index;
        }
        // 使用递归求和
        return fibonacci1(index - 1) + fibonacci1(index - 2);
    }

算法二：使用 for 循环求和（性能更高）

0、1、1、2、3、5、8、13、21、34、……n
n = 2 ：F(2) = F(1) + F(0)，循环1次
n = 3 : F(3) = F(2) + F(1)，循环2次
n = 4 ：F(4) = F(3) + F(2)，循环3次
...
n ：F(n) = F(n - 1) + F(n - 2)，循环n-1次

    /**
     * 斐波那契数列（算法二）
     * @param index 下标位置
     * @return index 位置的数值
     * 下标：0、1、2、3、4、5、6、7、  8、 9、.... n
     * 数值：0、1、1、2、3、5、8、13、21、34
     */
    private static Integer fibonacci2(Integer index) {
        Integer first = 0;
        Integer second = 1;
        if (index < 2) {
            return index;
        }
        /**
         * 求index位置上的数值，其实就是求 index-1 和 index-2 位置上的数值之和
         *
         * 所以可以通过遍历来实现
         */
        Integer sum = 0;
        for (int i = 1; i < index; i++) {
            sum = first + second;
            first = second;
            second = sum;
        }
        return sum;
    }

算法二代码优化

    /**
     * 斐波那契数列（算法二）
     * @param index 下标位置
     * @return index 位置的数值
     * 下标：0、1、2、3、4、5、6、7、  8、 9、.... n
     * 数值：0、1、1、2、3、5、8、13、21、34
     */
    private static Integer fibonacci2(Integer index) {
        Integer first = 0;
        Integer second = 1;
        if (index < 2) {
            return index;
        }
        /**
         * 求index位置上的数值，其实就是求 index-1 和 index-2 位置上的数值之和
         *
         * 所以可以通过遍历来实现
         */
        for (int i = 1; i < index; i++) {
            second += first;
            first = second - first;
        }
        return second;
    }

测试算法

    public static void main(String[] args) {
        Integer n = 10;
        long startTime = System.currentTimeMillis();
        Integer integer = fibonacci1(n);
//        Integer integer = fibonacci2(n);
        long endTime = System.currentTimeMillis();
        long tiem = endTime - startTime;
        System.out.println("下标为 " + n + "的数据为：" + integer + " 用时：" + tiem);
    }

• 测试结果如下，通过测试结果可以算法二的性能更高

当n = 10时
算法一：下标为 10的数据为：55 用时：0ms
算法二：下标为 10的数据为：55 用时：0ms
当n = 20时
算法一：下标为 20的数据为：6765 用时：2ms
算法二：下标为 20的数据为：6765 用时：0ms
当n = 30时
算法一：下标为 30的数据为：832040 用时：42ms
算法二：下标为 30的数据为：832040 用时：0ms
当n = 40时
算法一：下标为 40的数据为：102334155 用时：1751ms
算法二：下标为 40的数据为：102334155 用时：0ms
当n = 48时
算法一：下标为 48的数据为：512559680 用时：62664ms
算法二：下标为 48的数据为：512559680 用时：0ms

二、算法的好坏

一般从以下纬度来评估算法的优劣

• 正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
• ：估算程序指令的执行次数（执行时间）
• ：估算所需占用的存储空间

三、大O表示法

一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度

忽略常数、系数、低阶

• 9 O(1)
• 2n + 1 O(n)
• n² + 2n +2 O(n²)
• 3n³ + 2n² + 1n +100 O(n³)

注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率 时间复杂度大O表示法.png

• 复杂度表
• 复杂度-小规模数据 复杂度-小规模数据.png
• 复杂度-大规模数据 复杂度-大规模数据.png

斐波那契数列的时间复杂度

0、1、2、3、4、5、6、7、8、。。。n
0、1、1、2、3、5、8、13、21、34...

算法一的时间复杂度 算法一-时间复杂度1.png

算法一-时间复杂度2.png

• 当n=5时，约等于 2^(n-1)（20+2¹⁺²2+2^3-2+24-14 = 2⁰⁺²1+2²⁺²3+2^4-16）
• 当n=6时，约等于 2^(n-1)（20+2¹⁺²2+2³⁺²4-8+2^5-30 = 2⁰⁺²1+2²⁺²3+2⁴⁺²5-38）
• 所以算法一的时间复杂度为O(2^n)

算法二的时间复杂度

n = 2 ：F(2) = F(1) + F(0)，循环1次
n = 3 : F(3) = F(2) + F(1)，循环2次

n = 4 ：F(4) = F(3) + F(2)，循环3次
...
n ：F(n) = F(n - 1) + F(n - 2)，循环n-1次

• 所以算法二的时间复杂度为O(n)