Liang2uv's blog Liang2uv's blog
首页
  • 前端文章

    • JavaScript
    • Vue
    • 面试总结
  • 学习笔记

    • 《JavaScript教程》笔记
    • 《ES6 教程》笔记
    • 《Vue》笔记
    • 小程序笔记
    • TypeScript笔记
    • 数据结构笔记
    • mongoDB笔记
    • nginx笔记
  • HTML
  • CSS
  • 技术文档
  • GitHub技巧
  • Nodejs
  • 博客搭建
  • 分类
  • 标签
  • 归档
  • 网站
  • 资源
  • 关于
  • 作品集

Liang2uv

我也想成为前端大佬
首页
  • 前端文章

    • JavaScript
    • Vue
    • 面试总结
  • 学习笔记

    • 《JavaScript教程》笔记
    • 《ES6 教程》笔记
    • 《Vue》笔记
    • 小程序笔记
    • TypeScript笔记
    • 数据结构笔记
    • mongoDB笔记
    • nginx笔记
  • HTML
  • CSS
  • 技术文档
  • GitHub技巧
  • Nodejs
  • 博客搭建
  • 分类
  • 标签
  • 归档
  • 网站
  • 资源
  • 关于
  • 作品集
  • 第一章:数据结构
  • 第二章:算法
    • 算法
      • 定义
      • 特性
      • 算法设计要求
      • 算法效率的度量方法
      • 时间复杂度
      • 空间复杂度
  • 第三章:线性表
  • 第四章:栈
  • 第五章:队列
  • 第六章:串
  • 第七章:树
  • 第八章:图
  • 第九章:查找
  • 第十章:排序
  • 《数据结构》笔记
Liang2uv
2020-11-05

第二章:算法

# 第二章:算法

# 算法

# 定义

  • 算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作

# 特性

  • 输入:0或多个
  • 输出:1个或多个
  • 有穷性
  • 确定性
  • 可行性

# 算法设计要求

  • 正确性
  • 可读性
  • 健壮性
  • 时间效率高和存储量低

# 算法效率的度量方法

  • 事后统计法:对运行时间进行比较
  • 事前估计法

# 时间复杂度

  • 在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。记作:T(n)=O(f(n))
  • 大O记法
  • T(n)增长最慢的算法是最优算法

# 推导大O记法

  • 常数阶:O(1),例如:O(12)=O(1)

  • 线性阶:O(n)

    int i;
    for(i = 0; i < n; i++)
    {
        // TODO
    }
    
    1
    2
    3
    4
    5
  • 对数阶:O(logn)

    int count = 1;
    while(count < n)
    {
        count = count * 2;
    }
    
    1
    2
    3
    4
    5

    计算方式:,即,所以

  • 平方阶:O(m * n)

    int i, j;
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < n; j++)
        {
            // TODO
        }
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
  • 立方阶:O(),例如:()

  • 指数阶:O()

  • nlogn阶:O(nlogn),例如

耗费时间:O(1)<O(logn)<O(n)<O(nlogn)<O()<O()<O()<O(n!)<O()

# 空间复杂度

  • 定义:以空间换取时间,记作:S(n)= O(f(n))
#数据结构#考研
上次更新: 2020/11/05, 15:11:00
第一章:数据结构
第三章:线性表

← 第一章:数据结构 第三章:线性表→

最近更新
01
第十章:排序
11-05
02
第九章:查找
11-05
03
第八章:图
11-05
更多文章>
Theme by Vdoing | Copyright © 2020-2021 Liang2uv | 桂ICP备19012079号-1
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式