【数据结构】P1 数据结构是什么、算法怎样度量

在这里插入图片描述

1.1 基本概念与术语

  • 数据: 数据是信息的载体,是所有能被计算机识别以及处理的符号。
  • 数据元素: 数据元素是数据基本单位,由若干 数据项 组成,数据项是构成数据元素最小的单位。
    • e . g . e.g. e.g. 数据元素如一条学生记录,数据项则为其中学号、姓名、性别等属性;
  • 数据对象: 数据对象是具有相同性质的数据元素的集合。
    • e . g . e.g. e.g. 小明是班级1学生,小红也是班级1学生,有集合 班级 1 = 小明 , 小红 , . . . . 班级1={小明, 小红, ....} 班级1=小明,小红,....
  • 数据类型: 分为原子类型、结构类型以及抽象数据类型;
    • 原子类型: 其值不可再分的数据类型;
    • 结构类型: 其值可以再分解为若干成分的数据类型;
    • 抽象数据类型
  • 数据结构: 数据结构描述数据元素相互之间的关系,包括三方面内容:逻辑结构、存储结构和数据的运算。

1.2 数据结构三要素

数据结构的三要素为:逻辑结构、存储结构、数据的运算;

1.2.1 逻辑结构

逻辑结构指数据元素之间的逻辑关系,从逻辑关系上描述数据,分为线性结构与非线性结构。

在这里插入图片描述

线性表是典型的线性结构,树和图是典型的非线性结构。

1.2.2 存储结构

存储结构指数据结构在计算机中的表示,也称物理结构,是用计算机实际实现的逻辑结构,主要有顺序存储、链式存储、索引存储和散列存储。

  • 顺序存储:逻辑上相邻的元素存储在物理位置也相邻的存储单元中。
    • 优点:可以实现随机存取,每个元素占用最小的存储空间。
    • 缺点:只能使用相邻的一整块存储单元,会导致出现较多的外部碎片。
  • 链式存储: 不要求逻辑上相邻的元素在物理位置上也相邻,借助指示元素存储位置的指针来表示元素之间的逻辑关系。
    • 优点:不会出现外部碎片,能充分利用全部存储单元。
    • 缺点:存储指针会额外占用存储空间,且只能顺序存取。
  • 索引存储: 另建立索引表,其中每一项为索引项,一般形式为:关键字、地址。
    • 优点:检索速度快。
    • 缺点:索引表额外占用存储空间,且增加、删除数据时也需修改索引表的时间成本。
  • 散列存储: 根据元素的关键字计算该元素的存储地址,又称为哈希存储。
    • 优点:检索、增加和删除结点操作快。
    • 缺点:若散列函数不好,会导致存储单元冲突,解决冲突需要额外的时间和空间开销。

1.2.3 数据的运算

施加在数据上的运算包含运算的定义和实现。

  • 运算的定义 是针对逻辑结构的,指出运算的功能。
  • 运算的实现 是针对存储结构的,指出运算的步骤。

2.1 算法定义

在这里插入图片描述

算法(Algorithm)是对特定问题求解步骤的一种描述,是指令的有限序列,其中每条指令表示一个或者多个操作。

2.2 算法五大特征

  • 有穷性: 一个算法必须在执行有穷步骤之后结束,且每一步都在有穷时间内完成。
  • 确定性: 算法中每条指令必须有明确的含义,对于相同的输入只能得出相同的输出。
  • 可行性: 算法中操作可以通过已经实现的基本运算执行有限次来实现。
  • 输入: 一个算法有零个或者多个输入。
  • 输出: 一个算法有一个或者多个输出。

一个好的算法,通常应考虑如下目标:

  • 正确性: 算法应能正确的解决问题。
  • 可读性: 算法应具有良好的可读性,简单的结构,同时带有标注帮助人们理解。
  • 健壮性: 输入非法数据时,算法应能对其做出反应和处理,而不会意外退出或者输出莫名结果。
  • 高效率与低存储量: 效率是指算法执行的时间,存储量是指算法执行中所需的最大存储空间。

2.3 算法效率度量

2.3.1 时间复杂度

一个语句的频度指的是该语句在算法中被重复执行的次数。算法中所有语句的频度之和为 T ( n ) T(n) T(n),时间复杂度分析 T ( n ) T(n) T(n) 的数量级。

算法的时间复杂度记为: T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))
其中 O O O 的含义表示数量级。

需要注意的是,算法的时间复杂度不仅仅取决于算法的结构规模,还取决于待输入数据的初始状态。对于同一个算法,因初始状态不同,结果可以为 O ( n ) O(n) O(n) 也可能为 O ( 1 ) O(1) O(1)
其中 O ( n ) O(n) O(n) 我们其为 “最坏时间复杂度” O ( 1 ) O(1) O(1) 称为 “最好时间复杂度”,而 “平均时间复杂度” 则为当所有可能输入实例在等概率出现的情况下,算法的期望运行时间。

** 在分析一个程序的时间复杂度时,有以下两条规则:

  1. 加法规则:
    T ( n ) = T 1 ( n ) + T 2 ( n ) = O ( f ( n ) ) + O ( g ( n ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n), g(n))) T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

  2. 乘法规则:
    T ( n ) = T 1 ( n ) ∗ T 2 ( n ) = O ( f ( n ) ) ∗ O ( g ( n ) ) = O ( f ( n ) ∗ g ( n ) ) T(n)=T_1(n)*T_2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)) T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)g(n))

常见的渐进时间复杂度为:
O ( 1 ) < O ( l o g 2 n ) < O ( n ) < O ( n l o g 2 n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)


2.3.2 空间复杂度

算法的空间复杂度 S ( n ) S(n) S(n) 为该算法所耗费的存储空间,记为 S ( n ) = O ( g ( n ) ) S(n)=O(g(n)) S(n)=O(g(n))

一个程序执行时除需要存储空间来存放本身的指令、常数、变量和输入数据外,还需要一些数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。

算法原地工作是指算法所需的辅助空间为常量,即为 O ( 1 ) O(1) O(1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/337665.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

云动态摘要 2024-05-31

给您带来云厂商的最新动态&#xff0c;最新产品资讯和最新优惠更新。 最新优惠与活动 [1.5折起]年中盛惠--AI分会场 腾讯云 2024-05-30 人脸核身、语音识别、文字识别、数智人、腾讯混元等热门AI产品特惠&#xff0c;1.5折起 云服务器ECS试用产品续用 阿里云 2024-04-14 云…

HTML 转义字符(escape characters)及其对应的符号(symbols)

以下是常见的 HTML 转义字符及其对应的符号&#xff0c;这些可以用于在 HTML 或 JSX 中避免解析错误和特殊字符的冲突&#xff1a; 空格 ( ): 或 引号: 单引号&#xff08;&#xff09;&#xff1a;&apos;、&lsquo;、、&rsquo;双引号&#xff08;"&#x…

AI 网页解锁器,用于网页抓取一切 | 最快的验证码解决服务

想象一下&#xff0c;解锁互联网的全部潜力&#xff0c;数据自由流动&#xff0c;没有任何障碍阻挡你获取所需信息。在网络爬虫的世界里&#xff0c;这个梦想常常会遇到障碍&#xff1a;CAPTCHA和反机器人措施&#xff0c;这些措施旨在保护网站免受自动化访问的侵害。但如果有一…

前端传String字符串 后端使用enun枚举类出现错误

情况 前端 String 后端 enum 前端 后端 报错 2024-05-31T21:47:40.61808:00 WARN 21360 --- [nio-8080-exec-6] .w.s.m.s.DefaultHandlerExceptionResolver : Resolved [org.springframework.web.method.annotation.MethodArgumentTypeMismatchException: Failed to con…

[数据集][目标检测]红外车辆检测数据集VOC+YOLO格式13979张类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;13979 标注数量(xml文件个数)&#xff1a;13979 标注数量(txt文件个数)&#xff1a;13979 标…

C++程序命令行参数学习

argc是参数个数&#xff1b; argv[0]是程序名&#xff0c;argv[1]是第一个参数&#xff1b; 如果输入osgptr1 x &#xff0c;osgptr1是程序名&#xff0c;argc是2&#xff1b; 不算程序名&#xff0c;实际的参数个数是argc-1&#xff1b; #include <iostream>using …

STM32 入门教程(江科大教材)#笔记2

3-4按键控制LED /** LED.c**/ #include "stm32f10x.h" // Device headervoid LED_Init(void) {/*开启时钟*/RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA, ENABLE); //开启GPIOA的时钟/*GPIO初始化*/GPIO_InitTypeDef GPIO_InitStructure;GPIO_I…

Python魔法之旅-魔法方法(08)

目录 一、概述 1、定义 2、作用 二、应用场景 1、构造和析构 2、操作符重载 3、字符串和表示 4、容器管理 5、可调用对象 6、上下文管理 7、属性访问和描述符 8、迭代器和生成器 9、数值类型 10、复制和序列化 11、自定义元类行为 12、自定义类行为 13、类型检…

用万界星空科技低代码平台能快速搭建一个云MES系统

一、低代码平台与MES:智能制造的新篇章 随着工业4.0和智能制造的兴起&#xff0c;企业对于生产过程的数字化、智能化需求日益迫切。传统的MES系统实施周期长、成本高&#xff0c;成为许多企业数字化转型的瓶颈。而低代码开发平台的出现为这一问题提供了新的解决思路。 二、万界…

Vue.js - 生命周期与工程化开发【0基础向 Vue 基础学习】

文章目录 Vue 的生命周期Vue 生命周期的四个阶段Vue 生命周期函数&#xff08;钩子函数 工程化开发 & 脚手架 Vue CLI**开发 Vue 的两种方式&#xff1a;**脚手架目录文件介绍项目运行流程组件化开发 & 根组件App.vue 文件&#xff08;单文件组件&#xff09;的三个组成…

【PostgreSQL17新特性之-explain命令新增选项】

EXPLAIN是一个用于显示语句执行计划的命令&#xff0c;可用于显示以下语句类型之一的执行计划&#xff1a; - SELECT - INSERT - UPDATE - DELETE - VALUES - EXECUTE - DECLARE - CREATE TABLE AS - CREATE MATERIALIZED VIEWPostgreSQL17-beta1版本近日发布了&#xff0c;新…

微信小程序-页面导航-导航传参

1.声明式导航传参 navigator组件的url属性用来指定将要跳转到的页面的路径&#xff0c;同时&#xff0c;路径的后面还可以携带参数&#xff1a; &#xff08;1&#xff09;参数与路径之间使用 ? 分割 &#xff08;2&#xff09;参数键与参数值用 相连 &#xff08;3&…

四汇聚荣科技是靠谱的吗?

在当今这个科技飞速发展的时代&#xff0c;新兴科技公司如同雨后春笋般涌现。其中&#xff0c;四汇聚荣科技引起了人们的关注。许多人好奇&#xff0c;这家公司是否靠谱?它能否在激烈的市场竞争中站稳脚跟?接下来&#xff0c;让我们从四个不同的方面来深入探讨这个问题。 一、…

VB.net 进行CAD二次开发(二)

利用参考文献2&#xff0c;添加面板 执行treeControl New UCTreeView()时报一个错误&#xff1a; 用户代码未处理 System.ArgumentException HResult-2147024809 Message控件不支持透明的背景色。 SourceSystem.Windows.Forms StackTrace: 在 System.Windows…

java调用科大讯飞离线语音合成SDK --内附完整项目

科大讯飞语音开放平台基础环境搭建 1.用户注册 注册科大讯飞开放平台账号 2.注册好后先创建一个自己的应用 创建完成后进入应用选择离线语音合成&#xff08;普通版&#xff09;可以看到我们开发需要的SDK,选择windows MSC点击下载。 3.选择你刚刚创建的应用&#xff0c;选择…

react 怎样配置ant design Pro 路由?

Ant Design Pro 是基于 umi 和 dva 的框架&#xff0c;umi 已经预置了路由功能&#xff0c;只需要在 config/router.config.js 中添加路由信息即可。 例如&#xff0c;假设你需要为 HelloWorld 组件创建一个路由&#xff0c;你可以将以下代码添加到 config/router.config.js 中…

物联网应用系统与网关

一. 传感器底板相关设计 1. 传感器设计 立创EDA传感器设计举例。 2. 传感器实物图 3. 传感器测试举例 测试激光测距传感器 二. 网关相关设计 1. LORA&#xff0c;NBIOT等设计 2. LORA&#xff0c;NBIOT等实物图 3. ZigBee测试 ZigBee测试 4. NBIoT测试 NBIoT自制模块的测试…

VS2022+QT5.15.2+MySQL8.4大集合

网上的教程都建议用Qt5&#xff0c;不要用6&#xff0c;不死心的尝试了整整一天失败了&#xff0c;乖乖用回5&#xff0c;qt5需要编译一下生成mysql的动态和静态库 1. mysql8.4安装 下载社区开发版&#xff0c;注意要64位 https://dev.mysql.com/downloads/mysql/ 配置一下数…

单链表实现通讯录

之前我们完成了基于顺序表&#xff08;动态&#xff09;实现通讯录&#xff0c;现在我们链表学完了&#xff0c;可以尝试着使用链表来实现我们的通讯录。 首先我们要明白我们写的通讯录是由一个个节点组成的&#xff0c;每个节点里存储的就是我们的联系人信息。也就是说 我们需…

mysql大表的深度分页慢sql案例(跳页分页)-2

1 背景 有一张大表&#xff0c;内容是费用明细表&#xff0c;数据量约700万级&#xff0c; 普通B树索引KEY idx_fk_fymx_qybh_xfsj (qybh,xfsj)。 1.1 原始深度分页sql select t.* from fk_fymx t where t.qybh XXXXXXX limit 100000,100; 深度分页会导致加载数据行过多1000001…