美文网首页数据结构与算法
数据结构第一季 Day01 算法复杂度

数据结构第一季 Day01 算法复杂度

作者: 望穿秋水小作坊 | 来源:发表于2021-02-24 07:53 被阅读0次

    一、 初识算法

    1. 算法用来做什么？解决同一个问题，不同的算法效率可能差距会很大吗？
    • 算法是用来解决特定问题的一系列的执行步骤
    • 不同的算法效率，差距是巨大的 
        // 计算 a 跟 b 的和
    public static int plus(int a, int b) {
        return a + b;
    }
    // 计算 1+2+3+4+...+n 的和
    public static int sum(int n) {
        int result = 0;
        for (int i = 1; i < n; i++) {
            result += i;
        }
        return result;
    }
    2. 斐波那契数列的计算，递归思路的代码如下，会有什么问题？
        /*
     *  0 1 1 2 3 5 8 13 ...
     */
    public static int fib1(int n) {
        if (n <= 1) {
            return n;
        }
        return fib1(n - 1) + fib1(n - 2);
    }
    • 这应该是最容易想到的算法了，但是，我们看到当计算 64 的时候，程序已经住了，算不出来结果了。
    3. 斐波那契数列的计算，我们换一种求和算法的代码如下，依然会有问题吗？
        /*
     *  0 1 1 2 3 5 8 13 ...
     */
    
    public static int fib2(int n) {
        if (n <= 1) return n;
        
        int first = 0;
        int second = 1;
        int sum = 0;
        for (int i = 1; i < n; i++) {
            sum = first + second;
            first = second;
            second = sum;
        }
        return sum;
    }
    • 这个计算速度就非常快了，即使 n = 64 也能瞬间计算出来
    4. 思考，如果是你，你会怎么量化的对比两个算法的效率？
    • 写一个时间统计的工具类
    package com.lsp;

public class Times {
    public interface Block {
        void runBlock();
    }
    
    public static void execute(String taskName,Block block) {
        long startTime = System.currentTimeMillis();
        block.runBlock();
        long endTime = System.currentTimeMillis();
        System.out.println("===========================");
        System.out.println("【" + taskName + "】");
        System.out.println("耗时：" + (endTime - startTime) / 1000.0 + "秒");
    }
}
    • 调用时间统计的工具类
        public static void main(String[] args) {
        int n = 43;
        Times.execute("fib1", new Block() {
            @Override
            public void runBlock() {
                fib1(n);
            }
        });
        Times.execute("fib2", new Block() {
            @Override
            public void runBlock() {
                fib2(n);
            }
        });
    }
    • 输出结果如下
    ===========================
【fib1】
耗时：1.703秒
===========================
【fib2】
耗时：0.0秒
    • 这种方案也叫做：事后统计法

    二、 算法复杂度

    1. 上一个方案评判算法复杂度有什么明显缺点？如何评判一个算法的好坏（从一个前提、两个维度来说）？
    • 上述方案的明显缺点：
    • ① 执行时间严重依赖硬件以及运行时各种不确定的因素
    • ② 必须编写响应的测算代码
    • ③ 测试数据的选择比较难保证公正性
    • 评判算法的好坏：
    • 一个前提：正确性、可读性、健壮性
    • 两个维度：
    • ① 时间复杂度： 估算程序指令的执行次数（执行时间）
    • ② 空间复杂度： 估算所需占用的存储空间
    2. 用你的知识，计算一下下面代码的执行次数？我发现 log 这个函数，需要再去巩固下，忘记了~~
    • 问题如下
        public static void test1(int n) {
        if (n > 10) { 
            System.out.println("n > 10");
        } else if (n > 5) { // 2
            System.out.println("n > 5");
        } else {
            System.out.println("n <= 5"); 
        }
        
        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }
    }

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

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

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

    public static void test5(int n) {
        while ((n = n / 2) > 0) {
            System.out.println("test");
        }
    }

    public static void test6(int n) {
        while ((n = n / 5) > 0) {
            System.out.println("test");
        }
    }

    public static void test7(int n) {
        for (int i = 1; i < n; i = i * 2) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test10(int n) {
        int a = 10;
        int b = 20;
        int c = a + b;
        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + c);
        }
    }
    • 答案如下
        public static void test1(int n) {
        // 汇编指令
        
        // O(1)
        if (n > 10) { 
            System.out.println("n > 10");
        } else if (n > 5) { // 2
            System.out.println("n > 5");
        } else {
            System.out.println("n <= 5"); 
        }
        
        // 1 + 4 + 4 + 4
        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }
        
        // 140000
        // O(1)
    }

    public static void test2(int n) {
        // O(n)
        // 1 + 3n
        for (int i = 0; i < n; i++) {
            System.out.println("test");
        }
    }

    public static void test3(int n) {
        // 1 + 2n + n * (1 + 3n)
        // 1 + 2n + n + 3n^2
        // 3n^2 + 3n + 1
        // O(n^2)
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test4(int n) {
        // 1 + 2n + n * (1 + 45)
        // 1 + 2n + 46n
        // 48n + 1
        // O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 15; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test5(int n) {
        // 8 = 2^3
        // 16 = 2^4
        
        // 3 = log2(8)
        // 4 = log2(16)
        
        // 执行次数 = log2(n)
        // O(logn)
        while ((n = n / 2) > 0) {
            System.out.println("test");
        }
    }

    public static void test6(int n) {
        // log5(n)
        // O(logn)
        while ((n = n / 5) > 0) {
            System.out.println("test");
        }
    }

    public static void test7(int n) {
        // 1 + 2*log2(n) + log2(n) * (1 + 3n)
        
        // 1 + 3*log2(n) + 2 * nlog2(n)
        // O(nlogn)
        for (int i = 1; i < n; i = i * 2) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test10(int n) {
        // O(n)
        int a = 10;
        int b = 20;
        int c = a + b;
        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + c);
        }
    }
    3. 大 O 表示法是忽略了三个什么因素？对数要注意什么？
    • 一般用大 O 表示法描述复杂度，它表示的是数据规模 n 对应的复杂度
    • 忽略 常数、系数、低阶
    • 注意：大 O 表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的好坏。
    image.png image.png
    4. 常见的复杂度（至少列举三个）？
    image.png
    5. 实战：自行计算斐波那契数列两种算法的时间复杂度，你能算出来吗？
    image.png
    • 有时候算法之间的差距，往往比硬件的差距还要大

    相关文章

      网友评论

        本文标题：数据结构第一季 Day01 算法复杂度

        本文链接：https://www.haomeiwen.com/subject/hfvdfltx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        数据结构与算法

        关于我们|服务条款|联系我们|数据结构第一季 Day01 算法复杂度|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！