复杂度分析

复杂度分析

斐波那契函数

0 1 2 3 4 5 6 7 0 1 1 2 3 5 8 13 ....

某个位置的数为前两个数之和

    // 递归
    // O(n^2)
    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }

        return fib(n - 1) + fib(n - 2);

    }
    
    // 非递归
    // O(n)
    public static int fib2(int n) {
        if (n <= 1) {
            return n;
        }

        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        
//      while (n-- > 1) {
//          second += first;
//          first = second - first;
//      }
        
        return second;

    }

复杂度变化 复杂度变化

算法优化方向

• 用尽量少的存储空间

• 用尽量少的执行步骤

  时间换空间

  空间换时间

评估算法的优劣

• 正确性

• 可读性

• 健壮性(对不合理输入的反应能力和处理能力)

• 时间复杂度: 估算程序指令的执行次数. 执行时间

• 空间复杂度, 估算所需占用空间

其他情况

• 最好最坏复杂度

• 均摊复杂度

• 复杂度震荡

• 平均复杂度

斐波那契的另一种实现方式--线性代数解法, 特征方程

特征方程解法