Jared's blog Jared's blog
首页
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • Java
  • 数据库SQL
  • 设计模式
  • 集成开发环境
  • Linux系统
  • 代码管理
  • 项目管理
  • 后端

    • 中间件
    • Spring家族
    • 服务器软件
    • 数据库
    • 搜索引擎
    • 分布式&微服务
    • 容器化
  • 前端

    • 基础
    • 模板框架
    • 组件化框架
  • 运维知识
  • 部署工具
架构与模型
  • 在线教育
  • 电商
  • 疑惑日志
  • 随笔
  • 友链
  • 书籍
  • 娱乐
  • Github (opens new window)
  • Gitee (opens new window)
  • CSDN (opens new window)

Jared H

💻🤣😜
首页
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • Java
  • 数据库SQL
  • 设计模式
  • 集成开发环境
  • Linux系统
  • 代码管理
  • 项目管理
  • 后端

    • 中间件
    • Spring家族
    • 服务器软件
    • 数据库
    • 搜索引擎
    • 分布式&微服务
    • 容器化
  • 前端

    • 基础
    • 模板框架
    • 组件化框架
  • 运维知识
  • 部署工具
架构与模型
  • 在线教育
  • 电商
  • 疑惑日志
  • 随笔
  • 友链
  • 书籍
  • 娱乐
  • Github (opens new window)
  • Gitee (opens new window)
  • CSDN (opens new window)
  • 数据结构与算法

    • README
      • 概念
        • 算法复杂度
    • 数据结构

    • 算法

  • 计算机网络

  • 操作系统

  • Java

  • 数据库-SQL

  • 设计模式

README

# README

# 概念

程序 = 数据结构+ 算法

# 算法复杂度

算法的复杂性体现在运行该算法时计算机所需要的资源多少上 ,计算机资源最重要的是时间和空间(寄存器)资源,因此复杂度分为时间和空间复杂度

# 时间复杂度

是指执行算法所需要的计算工作量,指时间增长的趋势。T(n) = O( f ( n ) )

  • 常用时间复杂度量级:
    1. 常数阶O(1): 算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。

      int x = 0; 
      int y = 1; 
      int temp = x; 
      x = y ;
      y = temp;
      
      1
      2
      3
      4
      5

      该程序段的执行时间是一个与问题规模n无关的常数

    2. 对数阶 :由于计算机使用二进制的记数系统,对数常常以2为底(即 ,有时写作 )。然而,由对数的换底公式, 和 只有一个常数因子不同,这个因子在大O记法中被丢弃。因此记作 ,而不论对数的底是多少,是对数时间算法的标准记法。 典型的二分查找法:假如有32份试卷,你丢一次,还剩16份 ,丢两次,还剩下8 份,丢三次,就只剩下4份了,可以这么一直丢下去,丢到第五次,就只剩下一份了。而。也就是我们一次丢一半,总要丢到只有一份的时候才能出结果,如果有n份,那么显然我们就有

    3. 线性阶O(n): 随着样本数量的增加,复杂度也随之线性增加

      for(int i = 1;i<=n;i++){
          x++;    //O(1+3N)=O(N)
      }
      
      1
      2
      3
    4. 线性对数阶O(nlogN): 比如对一堆带有序号的书进行排序。先选一本,然后把号码大于这本书的扔右边,小于这本书的扔左边。因为每本书都要比较一次,所以这么搞一次的复杂度是 O(n),那么快排需要我们搞多少次呢?这个又回到了二分查找的逻辑了,每次都把书堆一分为二,请问分多少次手里才能只剩下一本书呢?答案还是logn。而从代码的角度来说,在到达大小为一的数列之前,我们也是需要作logn次嵌套的调用。

    5. 方阶: 计算的复杂度随着样本个数的平方数增长 在比如说构建一个网络,每个点都和其他的点相连。显然,每当我们增加一个点,其实就需要构建这个点和所有现存的点的连线,而现存的点的个数是n,所以每增加1,就需要增加n个连接,那么如果我们增加n个点呢,那这个连接的个数自然也就是 量级了。

    6. TODO

      • 立方阶
      • k次方阶
      • 指数阶
      • 阶乘 O( n!)

# 空间复杂度

是指对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势。S(n) = O( f ( n ) )

  • 常见的空间复杂度、、:
    1. O(1) 如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)

      int x = 0;
      int y = 0;
      x++;
      y++;
      
      1
      2
      3
      4

      代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

    2. O(n)

      int[] newArray = new int[n];
      for(int i = 0; i < 0; i++){
          newArray[i]=i;
      }
      
      1
      2
      3
      4

      上面这段代码中,new了一个数组出来,占用空间大小为n,后面的for循环只是给这个数组赋值并没有分配新的空间,因此这段代码的空间复杂度主要取决于 n 的大小。

    3. 比如说二维数组...

参考-JAVA全栈知识体系 (opens new window)

上次更新: 2022/04/01, 15:14:40
线性结构

线性结构→

Theme by Vdoing Copyright © 2020-2022 Jared H
粤ICP备20046800号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式
×