第一章 复杂度

什么是算法

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

以下算法是为了解决两数相加的问题。

// 计算a和b的和
public static int plue(int a, int b){
        return a + b;
}

//计算1+2+3+...+n的和
public static int sum(int n){
        int result = 0;
        for(int i = 1; i <= n; i++){
                result += i;
        }
        return result;
}

使用不同算法，解决同一个问题，效率可能相差非常大。

比如：求第 n 个斐波那契数（fibonacci number）

/**
 * @author xiexu
 * @create 2021-07-12 3:44 下午
 */
public class Main {

    /**
     * 斐波那契数列
     * 0 1 1 2 3 5 8 13 21 34 55 89
     */
    //时间复杂度：O(2^n)
    public static int fib1(int n) { //方法一：递归
        if (n <= 1) {
            return n;
        }
        return fib1(n - 1) + fib1(n - 2);
    }

    /**
     * 斐波那契数列
     * 0 1 1 2 3 5 8 13 21 34 55 89
     */
    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;
        }
        return second;
    }

    /**
     * 斐波那契数列
     * 0 1 1 2 3 5 8 13 21 34 55 89
     */
    public static int fib3(int n) { //方法三：非递归方法精简版
        if (n <= 1) {
            return n;
        }
        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            second += first;
            first = second - first;
        }
        return second;
    }

    //时间复杂度：O(n)
    public static void main(String[] args) {
        //测试两种方法的性能
        int n = 45;
        Times.test("fib1", new Times.Task() {
            @Override
            public void execute() {
                System.out.println(fib1(n));
            }
        });

        Times.test("fib2", new Times.Task() {
            @Override
            public void execute() {
                System.out.println(fib2(n));
            }
        });
    }
}

public class Times {
    private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");

    public interface Task {
        void execute();
    }

    public static void test(String title, Task task) {
        if (task == null) return;
        title = (title == null) ? "" : ("【" + title + "】");
        System.out.println(title);
        System.out.println("开始：" + fmt.format(new Date()));
        long begin = System.currentTimeMillis();
        task.execute();
        long end = System.currentTimeMillis();
        System.out.println("结束：" + fmt.format(new Date()));
        double delta = (end - begin) / 1000.0;
        System.out.println("耗时：" + delta + "秒");
        System.out.println("-------------------------------------");
    }
}

如何评判一个算法的好坏？

• 如果单从执行效率上进行评估，可能会想到这么一种方案：

  • 比较不同算法对同一组输入的执行处理时间
  • 这种方案也叫做：事后统计法

• 上述方案有比较明显的缺点：

  • 执行时间严重依赖硬件以及运行时各种不确定的环境因素
  • 必须编写相应的测算代码
  • 测试数据的选择比较难保证公正性

• 一般从以下维度来评估算法的优劣：

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

由于现在硬件发展的较好，一般情况下我们更侧重于时间复杂度。

大O表示法（Big O）

• 一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度。
• 忽略常数、系数、低阶：
  • 9 >> O (1)
  • 2n + 3 >> O (n)
  • n^2 + 2n + 6 >> O (n^2)
  • 4 n^3 + 3 n^2 + 22 n + 100 >> O (n^3)

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

对数阶的细节

常见的复杂度

fib1函数的时间复杂度分析

总结：

有时候算法之间的差距，往往比硬件方面的差距还要大

算法的优化方向

• 用尽量少的存储空间
• 用尽量少的执行步骤（执行时间）
• 根据情况，可以
  • 空间换时间
  • 时间换空间

多个数据规模的情况

public static void test(int n, int k){
        for(int i = 0; i < n; i++){
                System.out.println("test");
        }
        for (int i = 0; i < k; i++){
                System.out.println("test");
        }
}

分析：

时间复杂度：O(n + k)

LeetCode

首先去 https://leetcode-cn.com/ 注册一个力扣账号。

我们以力扣上一道斐波那契的题目为例，顺便分析算法的时间复杂度。

题目网址：LeetCode: 509.斐波那契数

斐波那契的线性代数解法 - 特征方程

最后

以上就是难过发夹最近收集整理的关于第一章 复杂度第一章 复杂度的全部内容，更多相关第一章内容请搜索靠谱客的其他文章。