数据结构(一)——概述

news/2024/4/21 13:26:27/文章来源:https://blog.csdn.net/a_rain2333/article/details/136453089

一、绪论

1.1数据结构的基本概念

数据:用来描述客观事物的数、计算机中是字符及所有能输入并被程序识别和处理的符号的集合。

数据元素:数据的基本单位,一个数据元素可由若干数据项组成。

数据结构:指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的三要素:逻辑结构、存储结构、数据的运算。

数据对象:具有相同性质的数据元素的集合,是数据的一个子集。

逻辑结构:指数据元素之间的逻辑关系

  • 集合:各个元素同属一个集合,别无其它关系。
  • 线性结构:数据元素之间是一对一的关系。
  • 树型结构:数据元素之间是一对多的关系。
  • 图状结构(网状结构):数据元素之间存在多对多的关系。

存储结构(物理结构):用计算机表示数据元素的逻辑关系(后三种统称为非顺序存储)

  • 顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
  • 链式存储:逻辑上相邻的元素在物理位置上可以不相邻,可借助指示元素存储地址的指针来表示元素之间的逻辑关系。
  • 索引存储:在存储元素信息的同时,建立附加的索引表。索引表中的每项称为索引项,索引项 的一般形式是(关键字,地址)。
  • 散列存储:根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。
  1. 若采用顺序存储,则各个数据元素在物理上必须是连续的;
    若采用非顺序存储,则各个数据元素在物理上可以是离散的。
  2. 数据的存储结构会影响存储空间分配的方便程度
  3. 数据的存储结构会影响对数据运算的速度

数据的运算:运算的定义是针对逻辑结构的, 指出运算的功能;运算的实现是针对存储结构的,指出运算的具体操作步骤。
例:结合现实需求定义队列这种逻辑结构的运算:
①队头元素出队; ②新元素入队; ③输出队列长度;

数据类型:数据类型是一个值的集合和定义在此集合上的一组操作的总称。
   1)原子类型。其值不可再分的数据类型
   2)结构类型。其值可以再分解为若干成分(分量)的数据类型

抽象数据类型(ADT):是抽象数据组织及与之相关的操作。

1.2算法和算法评价

1.2.1 算法的基本概念

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

算法的特性:有穷性、确定性、可行性、输入、输出。

  • 有穷性:一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成。
    用有限步骤解决某个特定的问题
  • 确定性:算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的输出。
  • 可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  • 输入:一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。
  • 输出:一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量。

算法的设计目标:正确性,可读性,健壮性,高效率与低存储量需求。

  • 正确性。算法应能够正确地解决求解问题。
  • 可读性。算法应具有良好的可读性,以帮助人们理解
  • 健壮性。输入非法数据时算法能适当地做出反应或进行处理,而不会产生莫名其妙的输出结果
  • 高效率与低存储量需求。花费时间少时间复杂度低;不费内存,空间复杂度低。

1.2.2 算法的时间复杂度

算法时间复杂度:事前预估算法时间开销T(n)与问题规模 n 的关系(T 表示 “time).

如何计算:

  1. 找到一个基本操作(最深层循环)
  2. 分析该基本操作的执行次数x与问题规模n的关系x=f(n)
  3. x的数量级O(x)就是算法时间复杂度T (n)

  T_{1}(n) = O(n); T_{2}(n) = O(n^{2}); T_{3}(n) = O(n^{3});

  大O表示“同阶”,同等数量级,即当n→∞时,二者之比为常数。

  结论:可以只考虑阶数高的部分,问题规模足够大时,常数项系数也可以忽略。

  常用技巧:

  a)加法规则

  T(n) = T_{1}(n) + T_{2}(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n))
  多项相加,只保留最高阶的项,且系数变为1

  b)乘法规则

  T(n) = T_{1}(n)×T_{2}(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))
  Eg:T_{3}(n)= n^{3}+ n^{2} log_{2}n = O( n^{3}) + O(n^{2} log_{2}n)
  多项相乘,都保留

   c)“常对幂指阶”  常数级<对数级<幂函数级<指数级<阶层级

   O(1) < O(log_{2}n) < O(n) < O(nlog_{2}n) < O(n^{2}) < O(n^{3}) < O(2^{n}) < O(n!) < O(n^{n})

三种时间复杂度:

  1. 最坏时间复杂度:最坏情况下算法的时间复杂度
  2. 平均时间复杂度:所有输入示例等概率出现的情况下,算法的期望运行时间
  3. 最好时间复杂度:最好情况下算法的时间复杂度 (一般不考虑)

1.2.3 算法的空间复杂度

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

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

相关文章

Spring整合Redisson(全是步骤,没有原理)

spring整合Redisson 添加依赖 <!--Redisson--><dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.10.3</version></dependency> <!-- redis --><dependency><…

【Python】5. 基础语法(3) -- 函数篇

函数 函数是什么 编程中的函数和数学中的函数有一定的相似之处. 数学上的函数, 比如 y sin x , x 取不同的值, y 就会得到不同的结果. 编程中的函数, 是一段可以被重复使用的代码片段 . # 代码示例: 求数列的和 # 1. 求 1 - 100 的和 sum 0 for i in range(1, 101):sum i…

交友盲盒系统PHP开源的盲盒源码

源码介绍&#xff1a; 交友盲盒系统是一款基于PHP开发的开源免费盲盒系统&#xff0c;旨在为用户提供一个充满乐趣和惊喜的社交体验。该系统具有丰富的功能和灵活的扩展性&#xff0c;可以轻松地满足各种线上交友、抽奖活动等场景的需求。 安装说明&#xff1a; PHP版本&…

如何开发云打印服务?云打印api怎么对接?

近来一段时间&#xff0c;云打印的火热让很多企业和第三方程序也想通过云打印服务来进行App的变现&#xff0c;尤其是一些学习类、工具类App&#xff0c;本身的变现方式较为单一&#xff0c;对于云打印服务的需求就更大了。那么我们该如何开发云打印服务&#xff1f;云打印api怎…

HarmonyOS—开启AOT编译模式

AOT&#xff08;Ahead Of Time&#xff09;即提前编译&#xff0c;能够在Host端&#xff08;即运行DevEco Studio的电脑&#xff09;将字节码提前编译成Target端&#xff08;即运行应用的设备&#xff09;可运行的机器码&#xff0c;这样字节码可以获得充分编译优化&#xff0c…

NLP:自定义模型训练

书接上文&#xff0c;为了完成指定的任务&#xff0c;我们需要额外训练一个特定场景的模型 这里主要参考了这篇博客&#xff1a;大佬的博客 我这里就主要讲一下我根据这位大佬的博客一步一步写下时&#xff0c;遇到的问题&#xff1a; 文中的cfg在哪里下载&#xff1f; 要不…

小白跟做江科大51单片机之DS1302可调时钟

原理部分 1.DS1302可调时钟介绍 单片机定时器主要占用CPU时间&#xff0c;掉电不能继续运行 图1 2.原理 图2 内部有寄存器&#xff0c;寄存的时候以时分秒寄存&#xff0c;以通信协议实现数据交互&#xff0c;就可以实现对数据进行访问和读写 3.主要寄存器定义 CE芯片使能…

Behavioral Verilog

行为Verilog Vivado synthesis支持行为Verilog硬件描述语言&#xff08;VHDL&#xff09;&#xff0c;除了如另外指出的。 行为Verilog中的变量 •行为Verilog中的变量声明为整数。 •这些声明仅用于测试代码。Verilog提供诸如reg和用于实际硬件描述的导线。 •reg和wire之…

NTP协议介绍

知识改变命运&#xff0c;技术就是要分享&#xff0c;有问题随时联系&#xff0c;免费答疑&#xff0c;欢迎联系&#xff01; 网络时间协议NTP&#xff08;Network Time Protocol&#xff09;是TCP/IP协议族里面的一个应用层协议&#xff0c;用来使客户端和服务器之间进行时…

Grafana dashboards as ConfigMaps

文章目录 1. 简介2. 创建 configmaps3. grafana 界面查看 1. 简介 将 Grafana 仪表板存储为 Kubernetes ConfigMap 相比传统的通过 Grafana 界面导入仪表板有以下一些主要优点: 版本控制&#xff1a; ConfigMap 可以存储在版本控制系统(如Git)中,便于跟踪和管理仪表板的变更历…

C++消息队列处理提高性能的方法

1 消息队列特点 在当前多数软件系统中,处理传递消息多用消息队列机制,他具有以下优点: 1. 异步通信:消息队列支持异步通信,发送者和接收者之间的解耦程度较高。发送者将消息放入队列后即可继续执行,而不需要等待接收者的响应。这样可以提高系统的吞吐量和处理能力。 2.…

docker部署SkyWalking+ES

1.ElasticSearch部署和安装 1.1去dockerHub官网&#xff08;https://hub.docker.com/&#xff09;搜索镜像 1.2 镜像拉取 docker pull elasticsearch:7.5.1 1.3镜像运行 视图切换到Overview 一直往下翻&#xff0c;就能看到启动命令&#xff1a; --net somenetwork是自定义网…

支持向量机 SVM | 线性可分:软间隔模型

目录 一. 软间隔模型1. 松弛因子的解释小节 2. SVM软间隔模型总结 线性可分SVM中&#xff0c;若想找到分类的超平面&#xff0c;数据必须是线性可分的&#xff1b;但在实际情况中&#xff0c;线性数据集存在少量的异常点&#xff0c;导致SVM无法对数据集线性划分 也就是说&…

看一看阿里云,如何把抽象云概念,用可视化表达出来。

云数据库RDS_关系型数据库 云数据库RDS_关系型数据库 专有宿主机 云数据库RDS_关系型数据库_MySQL源码优化版 内容协作平台CCP-企业网盘协同办公-文件实时共享

数据结构从入门到精通——栈

栈 前言一、栈1.1栈的概念及结构1.2栈的实现1.3栈的面试题 二、栈的具体实现代码栈的初始化栈的销毁入栈出栈返回栈顶元素返回栈中的元素个数检测是否为空Stack.hStack.ctest.c 前言 栈&#xff0c;作为一种后进先出&#xff08;LIFO&#xff09;的数据结构&#xff0c;在计算…

2.DOM-事件基础(注册事件、tab栏切换)(案例:注册、轮播图)

案例 注册事件 <!-- //disabled默认情况用户不能点击 --><input type"button" value"我已阅读用户协议(5)" disabled><script>// 分析&#xff1a;// 1.修改标签中的文字内容// 2.定时器// 3.修改标签的disabled属性// 4.清除定时器// …

3d合并的模型为什么没有模型---模大狮模型网

当合并多个3D模型后&#xff0c;发现合并后的模型没有显示任何内容或模型消失的情况通常有以下几个可能的原因&#xff1a; 蒙皮和骨骼绑定问题&#xff1a;如果合并的模型包含了蒙皮和骨骼动画&#xff0c;并且在合并过程中未正确处理这些信息&#xff0c;可能导致模型显示不出…

华为配置基于VLAN限速示例

华为配置基于VLAN限速示例 组网图形 图1 流量监管配置组网图 表1 Switch为上行流量提供的QoS保障 流量类型 CIR(kbps) PIR(kbps) DSCP优先级 语音 2000 10000 46 视频 4000 10000 30 数据 4000 10000 14 ^^^ 流分类简介配置注意事项组网需求配置思路操作步…

Linux服务器安装jdk

背景: 安装JDK是我们java程序在服务器运行的必要条件,下面描述几个简单的命令就可再服务器上成功安装jdk 命令总览: yum update -y yum list | grep jdk yum -y install java-1.8.0-openjdk java -version 1.查看可安装版本 yum list | grep jdk 2.如果查不到可先进行 yum upd…

手写分布式配置中心(三)增加实时刷新功能(短轮询)

要实现配置自动实时刷新&#xff0c;需要改造之前的代码。代码在https://gitee.com/summer-cat001/config-center​​​​​​​ 服务端改造 服务端增加一个版本号version&#xff0c;新增配置的时候为1&#xff0c;每次更新配置就加1。 Overridepublic long insertConfigDO(…