美文网首页学习提升模版Java web
数据结构与算法一(复杂度)

数据结构与算法一(复杂度)

作者: flowerflower | 来源:发表于2020-04-12 00:19 被阅读0次
😝

目录
一、什么是算法
二、如何评判一个算法的好坏
三、大O表示法
四、常见的复杂度

一、什么是算法

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

需求: 求第n个斐波那契数
分析:
斐波那契数列的排列是:1,1,2,3,5,8,13,21,34,55,89,144……
这个数列从第三项开始,每一项都等于前两项之和。

package com.hp;
import com.hp.Times.Task;
public class Main {

    public static void main(String[] args) {
        int n = 40;
        Times.check("fib", new Task() {
            @Override
            public void execute() {
                System.out.println(fib(n));
            }
        });
        
        Times.check("fib1", new Task() {
            @Override
            public void execute() {
                System.out.println(fib1(n));
            }
        });
        Times.check("fib2", new Task() {
            @Override
            public void execute() {
                System.out.println(fib1(n));
            }
        });
        Times.check("fib3", new Task() {
            @Override
            public void execute() {
                System.out.println(fib1(n));
            }
        });
        Times.check("fib4", new Task() {
            @Override
            public void execute() {
                System.out.println(fib1(n));
            }
        });

    }


    //递归形式  速度慢  O(2^n)
    public static  int fib(int n) {
         if (n <= 1) return n;
        return fib(n - 1) +  fib( n - 2 );
    }
    
    /**
     * 0 1 2 3 4 5 6     i
     * 0 1 1 2 3 5 8 13 ....
     * 求第2个波那契数 假设 i = 3  的时候 要加2次  0 + 1 = 1 1 + 1 = 2 
     * 求第3个波那契数 假设 i = 4  的时候 要加3次  0 + 1 = 1 1 + 1 = 2 1 + 2 = 3  
     */
    //计算速度快 O(n)
    public static  int fib1(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; //加完之后的结果要给下一次的second
             first = second;
             second = sum;
        }
         return second;
    }
    //计算速度快 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++) {
             second += first;
             first = second - first; 
        }
         return second;

    }
    //计算速度快 O(n)
    public static  int fib3(int n) {
         if (n <= 1) return n;
         int first = 0;
         int second = 1;
         while(n-- > 1) {
             second += first;
             first = second - first; 
        }
         return second;
    }
    
    //线性代数解法  计算速度最快 O(1)
    public static  int fib4(int n) {
    
        double c = Math.sqrt(5);
        return (int)((Math.pow((1+c)/2,n) - Math.pow((1-c)/2, n))/c);
    }
图片.png

如何评判一个算法的好坏

对同一组输入的执行处理时间(事后统计法)eg:求第n个斐波那契数

缺点:
1.执行时间严重依赖于硬件以及运行时各种不确定的环境因素(比如:CPU)
2.必须编写相应的测算代码
3.测试数据的选择比较难保证公正性

一般从以下维度来评估算法的优劣:
1.正确性、可读性、健壮性
2.时间复杂度:估算程序指令的执行次数(执行时间)
3.空间复杂度:估算所需占用的存储空间

三、大O表示法

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

//如何估算时间复杂度 学会估算时间复杂度 O表示估算的意思
    public static void test1(int n) {       
        // 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 = 13
        //i = 0  执行次数:1次
        // i++   执行次数:4次
        // i < 4 执行次数:4次
        //打印    执行次数:4次
        //O(1)
        
        for (int i = 0; i < 4; i++) {  
            System.out.println("test");
        }
    
    }

    public static void test2(int n) {
        // O(n)
        // 1 + 3n
        //i = 0  执行次数:1次
        // i++   执行次数:n次
        // i < n 执行次数:n次
        //打印    执行次数:n次
        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)
        
        // O(n)
        for (int i = 0; i < n; i++) {
            //外层for 执行n次
            //内存for 执行(1+3n)次
            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  则4 2 1
        // 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");
            }
        }
    }
忽略常数、系数、低阶
9 >> O(1)
2n+3 >> O(n)
n^2+2^n+6 >>O(n^2)
4n^3 + 3n^2 + 22n+100 >> O(n^3)  

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

对数阶的细节
  • 对数阶一般省略底数,eg:log2n = log29 ∗ log9n
    所以 log2n 、log9n 统称为 logn

四、常见的复杂度

常见的复杂度 性能从高到低 数据规模较小时性能图 数据规模较大时性能图

fib函数的时间复杂度分析

首先我们再次回顾一下代码

    //递归形式   2^n
    public static  int fib(int n) {
         if (n <= 1) return n;
        return fib(n - 1) +  fib( n - 2 );
        
    }
假设n=5
用大O表示法

相关文章

  • 数据结构与算法 - 查找

    数据结构与算法系列文章数据结构与算法 - 时间复杂度数据结构与算法 - 线性表数据结构与算法 - 树形结构数据结构...

  • 数据结构与算法 - 树形结构

    数据结构与算法系列文章数据结构与算法 - 时间复杂度数据结构与算法 - 线性表数据结构与算法 - 树形结构 目录 ...

  • 一位算法工程师的自我修养

    数据结构与算法 基本算法思想动态规划贪心算法回溯算法分治算法枚举算法 算法基础 时间复杂度 空间复杂度 最大复杂度...

  • 数据结构与算法

    数据结构与算法之美 数据结构与算法之美1--如何学数据结构与算法之美2--复杂度分析(上)数据结构与算法之美3--...

  • 数据结构与算法基本概念

    数据结构与算法 本文包括: 算法概念 时间复杂度 大 O 记法 数据结构概念 Python 内置类型的效率 算法的...

  • 数据结构学习大纲

    第一章 绪论 数据结构基本概念数据结构基本概念算法的基本概念算法的时间复杂度与空间复杂度分析基础时间复杂度分析空间...

  • 数据结构与算法之时间复杂度分析

    复杂度分析,是所有数据结构与算法的重中之重,复杂度分析是整个算法学习的精髓,只要掌握了它,可以说数据结构和算法的内...

  • 数据结构与算法-复杂度分析

    时间、空间复杂度:衡量算法执行小路的指标,数据结构与算法离不开时间、空间复杂度分析,复杂度分析是算法的精髓。 为什...

  • 数据结构与算法-C语言4-算法时间和空间复杂度

    数据结构与算法-目录 1.时间复杂度的定义 算法时间复杂度,也就是算法的时间量度。记作:T(n)=O(f(n))。...

  • 算法的复杂度分析

    本文是对极客时间《数据结构与算法之美》03-04 节课关于算法复杂度分析的小结。 前面:为什么要学习数据结构与算法...

网友评论

    本文标题:数据结构与算法一(复杂度)

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