当前位置: 首页 > news >正文

解码数据结构基础

数据结构基本概念

数据结构的核心是计算机存储和组织数据的方式,目的是提升后续数据访问效率,存储的通常是具有特定关系的数据集合。

核心术语定义

术语 定义 示例
数据(Data) 可输入计算机并被处理的符号总称 学生信息、数字、文本等
数据元素 数据的基本单位,计算机中作为整体处理 单个学生的完整信息
数据项 数据的最小单位,不可分割,组成数据元素 学生的学号、姓名、年龄
数据对象 多个相同类型数据元素的集合 一个班级所有学生的信息、世界上所有国家
数据结构 描述数据元素之间的逻辑结构(关系)和物理结构(存储方式) 数组(逻辑线性 + 物理顺序)、链表(逻辑线性 + 物理离散)

数据结构的两大构成

数据元素的逻辑关系物理关系无必然联系,可能同时存在、仅存一种或均不存在。

  • 逻辑结构:数据元素之间的逻辑关系,分 4 类:

    • 集合结构:元素间无任何关系(仅属于同一集合)
      集合

    • 线性结构:元素间为一对一关系(如排队队伍、学号序列)
      线性关系

    • 树状结构:元素间为一对多关系(如公司组织架构、家谱)
      树状结构

    • 图状结构:元素间为多对多关系(如社交网络、交通路线图)
      图状结构

  • 物理结构(存储结构):数据在计算机中的实际存储方式,分 2 类:

    • 顺序结构(连续存储):数据存于连续内存单元,可通过首地址计算任意元素地址(如数组)。
      顺序结构

    • 链式结构(离散存储):数据存于不连续内存单元,需通过指针 / 引用关联元素,无法直接计算后续元素地址(如链表)。
      链式结构

算法基础

算法是数据结构的 “操作逻辑”,二者结合构成程序(程序 = 数据结构 + 算法)。

算法定义

  • 广义:研究数据逻辑关系,选择存储方案并处理数据的过程。
  • 直白解释:解决问题的具体步骤(如排序算法 = 将无序数列变为有序的步骤)。

算法的 5 大特征

特征 要求
有穷性 程序需在有限次数内完成,且每步执行时间有限
确定性 每一条语句无歧义,相同输入必对应相同输出
可行性 复杂语句可分解为基本指令,且每条基本指令能在有限时间内完成
输入项 可包含 0 个或多个初始参数(0 个输入即无初始条件)
输出项 必须有 1 个或多个输出(无输出的算法无意义)

算法的衡量标准:复杂度

选择算法的核心是平衡时间复杂度空间复杂度(二者通常相互制约,“鱼和熊掌不可兼得”)。

时间复杂度

  • 定义:算法语句的执行次数(语句频度),而非实际运行时间(运行时间依赖 CPU 性能)。

  • 表示方法:用数学符号大 O () 表示,描述算法执行次数随数据规模(通常用n表示)增长的 “趋势”。

  • 计算技巧:

    • 只保留最高次项(最高次项对执行次数影响最大);
    • 舍弃最高次项的系数
    • 若结果为常数(与n无关),则时间复杂度为O(1)
  • 示例:

    // 示例1:n为数据规模
    for (int i=0; i < n; ++i) {  // 循环执行n次printf("hello\n");       // 核心语句执行n次
    }
    // 总执行次数:3n+2(多项式)→ 保留最高次项n,舍系数 → 时间复杂度O(n)`// 示例2:无数据规模n(固定次数)
    for (int i=0; i < 10; ++i) {  // 固定执行10次printf("hello\n");
    }
    // 总执行次数为常数 → 时间复杂度O(1)`
    

空间复杂度

  • 定义:算法运行期间所需的内存空间(包括存储数据、临时变量、指令等的空间)。
  • 原则:空间复杂度越小,算法对内存的占用越少,越优。

好算法的标准

  • 执行时间短(时间复杂度低)
  • 占用空间少(空间复杂度低)
  • 可读性好、易维护、可移植
http://www.hskmm.com/?act=detail&tid=16252

相关文章:

  • 软件工程学习日志2025.9.24
  • 大厂代码编写习惯简谈
  • 知识导航新体验:Perplexica+cpolar 24小时智能服务 - 教程
  • 《计算机算法设计与分析》系列--算法实现题1.1-统计数字问题
  • 银河麒麟系统root密码重置
  • 银河麒麟系统磁盘管理
  • 浅谈傅里叶级数
  • js遍历对象
  • day 10 (函数2 )
  • 入驻了爱发电
  • 奖励函数(双足)
  • 离线部署镜像仓库搭建
  • Temporal和Airflow有什么差别
  • lc1035-不相交的线
  • 自我介绍与未来规划
  • 解构React Server Components:服务端序列化与流式传输的底层逻辑
  • js里面的单引号、双引号及反引号的用法
  • 牛客刷题-Day4
  • Skinned Mesh Renderer与LOD系统蒙皮变形异常全解析
  • K8S (Containerd)初始化安装流程
  • ?模拟赛 赛后总结
  • 日志|动态规划|最长回文子串|最长公共子序列|HTML CSS
  • Java 字段命名避坑: success和isSuccess
  • OTA升级时软件异常复位问题分析
  • Atcoder Educational DP Contest 做题记录
  • 20250924
  • 跨端边云时序数据管理新范式:Apache IoTDB 的 DB+AI 融合之道 - 实践
  • 《Real-Time Rendering》第二章 图形渲染管线
  • 放弃Unity后,我为什么选择了Unigine?
  • PHP 与 Java 的终极对比:2025年,开发者该如何选择? - 详解