前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【数据结构】绪论

【数据结构】绪论

作者头像
陶然同学
发布2023-02-26 20:00:56
6360
发布2023-02-26 20:00:56
举报
文章被收录于专栏:陶然同学博客陶然同学博客

文章目录

1. 绪论

1.1 概述

1.2 数据与数据结构

1.2.1 术语

1.2.2 逻辑结构

1.2.3 存储结构:

1.2.4 数据操作:

1.3 算法

1.3.1 算法特性

1.3.2 算法目标

1.3.3 算法分析:概述

1.3.4 算法分析:时间复杂度(大O)

1.3.5 算法分析:最好、最坏、平均

1.4 回顾:西格玛Σ 求和

1. 绪论

1.1 概述

  • 算法 + 数据结构 = 程序
    • 程序:计算机指令的组合
    • 算法:程序的逻辑抽象
    • 数据结构:数据及其关系的反映,从逻辑结构和存储(物理)结构。
  • 数据结构解决具体问题:
    1. 数据的逻辑结构(数学模型)
    2. 数据的存储结构
    3. 数据操作与运算

1.2 数据与数据结构

1.2.1 术语

  • 数据(Data):数据是信息的载体,是对客观事物的符号表示。
  • 数据元素(Data Element):是数据的基本单位,是一个个体。相当于表的一行。
  • 数据项(Data Item):是数据元素的组成部分。相当于表的列。
  • 数据对象(Data Object):性质相同的数据元素的集合。相当于表。
  • 数据结构(Data Structure):特定关系的数据元素的集合。

1.2.2 逻辑结构

  • 逻辑结构:数据元素之间的逻辑关系,与数据存储无关,独立与计算机之外。
  • 数据元素按照特性:
    1. 集合:元素之间没有关系,比较松散
    2. 线性结构:元素之间存在==一对一==关系。除了开始和终端结点,其他结点由有一个前驱和一个后继。
    3. 树形结构:元素之间存在==一对多==关系。
    4. 图形结构:元素之间存在==多对多==关系。
  • 数据的逻辑结构需要2部分:数据元素(data)、数据元素的关系(relationship)

1.2.3 存储结构:

  • 存储结构:数据的存储结构,也称为物理结构,是数据的逻辑结构在计算机的实现。
    • 数据元素的值存储表示和逻辑关系。
  • 存储结构的4种方式:
    1. 顺序存储:在一片连续的存储空间中进行存储,元素的逻辑位置和物理位置保持一致。例如:数组
    1. 链式存储:可以存储在任意的物理物质上,需要额外的部分存放逻辑关系的指针。例如:链表
    1. 索引存储:存储数据的同时,额外的存储一个索引表。在查询时可以提高效率。
    2. 散列存储:一般情况物理上可以是连续的存储空间,需要通过散列函数hash来确定存储位置。在查询时可以提高效率。

1.2.4 数据操作:

  • 初始化:创建、销毁:
  • 数据操作:插入/添加、删除、修改
  • 数据使用:查找、遍历

1.3 算法

  • 算法:对特定问题求解步骤的一种描述。是指令的有限序列。

1.3.1 算法特性

  1. 有穷性:有限
  2. 确定性:需求确定、指令确定
  3. 有效性:指令都是由意义
  4. 输入:
  5. 输出:

1.3.2 算法目标

  1. 正确性:基本要求,需求和实现对应。
  2. 可读性:使程序员能够读懂,编写代码时可以辅助注释。
  3. 健壮性:临界值的处理、无效数据的校验等。
  4. 高效性:使用较少的资源(资源分2种:时间资源、空间资源)。一个好的算法要做到执行时所需时间尽量短,所需的最大存储空间尽量少。

1.3.3 算法分析:概述

  • 算法的复杂度是衡量算法优劣的重要依据。
  • 算法的复杂度分类:时间复杂度、空间复杂度。
    • 时间复杂度:执行时间的长短。
    • 空间复杂度:执行时空间需求量,也就是计算机资源的使用量。

1.3.4 算法分析:时间复杂度(大O)

  • 主要考虑因素:
    1. 算法本身
    2. 问题规模
    3. 程序语言选择
    4. 编译程序(JDK优劣)
    5. 硬件速度
    6. 运行软件
  • 时间复杂度通过大O表示法进行表示的
    • 大O表示法,用于估算一个算法的执行时间。
    • 算法执行时间:Σ(指令的执行次数 * 指令的执行时间)。
    • 指令的执行时间是固定的,可以不考虑。只需要考虑指令的执行次数即可。
    • 大O表达法,通过统计指令的执行次数,就可以估算出一个算法的优劣。
    • 指令的执行次数:每行代码执行的次数,将所有的次数累加在一起即可。
    • 例如1.7:2n^3 + 3n^2+2n+1 总次数表达式 --> 只考虑最高次幂 --> O(n^3)
    • 大O表达式只需要考虑最高次幂的项。
  • 大O表达式常见的形式
    • 常量阶:O(1) ,执行的次数与输入无关。
    • 线性阶:O(n) ,执行的次数与输入成正比关系。例如:一层循环。
    • 平方阶:O(n^2) , 执行的次数与输入成平方关系。例如:二层循环
    • 立方阶:O(n^3) ,执行的次数与输入成立方关系。例如:三层循环
    • 对数阶:O(log2n) , 执行的次数与输入成开方关系。例如:求对数 log28 = 3
    • 线性对数阶:O(nlog2n)
  • O(log2n) 指数计算:R表示次数
  • O (n) :一层循环
  • O(n^2):二层循环(99乘法表) int n = 9; for(int i = 0 ; i < n ; i ++) {    for(int j = 0 ; j < n : j ++) {        // 次数 n*n   } }
  • O(n^3):三层循环 int n = 9; for(int i = 0 ; i < n ; i ++) { //时针    for(int j = 0 ; j < n : j ++) { //分针        for(int m = 0 ; m < n ; m++) { //秒针            // 次数 n * n * n       }   } }

1.3.5 算法分析:最好、最坏、平均

  • 实例:从数组中获得内容 a[1...n]
  • 最好时间复杂度:获得最好的情况,例如:数组中的第一个数据。O(1)表示此情况。
  • 最坏时间复杂度:获得最坏的情况,例如:数据中最后一位。O(n)表示此情况。
  • 平均时间复杂度:
    • 1+...+n和 : (n+1) * n/2
    • 平均,和/n :(n+1) * n/2 / n ---> (n + 1) / 2 --> O(n)表示
  • 结论:在一般情况下,取最坏时间复杂度等概率下的平均时间复杂度作为算法的时间复杂度。

1.4 回顾:西格玛Σ 求和

  • 需求:1+2+3+4+....+n  
\sum_{i=1}^{n}\dfrac{(n+1)*n}{2} \tag{西格玛Σ求和}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-09-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 1. 绪论
    • 1.1 概述
      • 1.2 数据与数据结构
        • 1.2.1 术语
        • 1.2.2 逻辑结构
        • 1.2.3 存储结构:
        • 1.2.4 数据操作:
      • 1.3 算法
        • 1.3.1 算法特性
        • 1.3.2 算法目标
        • 1.3.3 算法分析:概述
        • 1.3.4 算法分析:时间复杂度(大O)
        • 1.3.5 算法分析:最好、最坏、平均
      • 1.4 回顾:西格玛Σ 求和
      相关产品与服务
      对象存储
      对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档