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

数据结构与算法(一):概述

数据结构学了有一年左右的时间了,但是一直没有详细地总结一下,现在回想起来,感觉有些内容忘记了。所以接下来一段时间我将重新归纳总结一下,算是温故而知新了。

一、数据结构

1、定义

数据结构是计算机存储、组织数据的方式。在现实世界中,不同数据元素之间不是独立的,而是存在特定关系的,我们将这些关系称为结构。同样在计算机中,数据元素也不是孤立、杂乱无序的,而是具有内在联系的数据集合。

数据元素之间存在的一种或多种特定关系,也就是数据的组织形式,叫数据结构。也可以说,数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。程序设计的实质就是数据结构和算法是设计,因此我们说程序设计 = 数据结构 + 算法

2、数据结构的几个术语

  • 数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。它不仅包括整型等数值类型,还包括字符、声音、图像等非数值类型。这些类型都具备两个特征:

    • 可以输入计算机
    • 能被计算机程序处理
  • 数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。也被称为记录。

  • 数据项:一个数据元素可以由若干个数据项组成。数据项是A数据的不可分割的最小单位。。

  • 数据对象:是性质相同的数据元素的集合,是数据的子集。

例如:一本书的书目信息为一个数据元素,而书目信息的每一项(如书名、作者名等)为一个数据项。

3、逻辑结构与物理结构

按照不同的角度,数据结构可分为逻辑结构和物理结构。其中逻辑结构是面向问题的,而物理结构是面向计算机的,它们的基本目标都是将数据及其逻辑关系存储到计算机内存中。

  • 逻辑结构:是指数据对象中数据元素之间的相互关系。分为四种:集合结构、线性结构、树形结构和图形结构。

在这里插入图片描述

  • 物理(存储)结构:是指数据的逻辑结构在计算机中的存储形式。数据的存储结构应正确反映数据元素之间的逻辑关系,这是关键。数据元素的存储结构可分为两种:顺序存储结构和链式存储结构。
    • 顺序存储结构:把数据元素放在地址连续的存储单元中,数据间的逻辑关系和物理关系一致。如,数组。
    • 链式存储结构:把数据元素放在任意的存储单元中,数据间使用指针关联。数据元素的存储关系不能反映其逻辑关系。如,链表。
      在这里插入图片描述
      同样的逻辑结构(线性、树形、图形、集合)既可以采用顺序存储结构也可以采用链式存储结构来存储数据和关系。存储结构的选择主要考虑算法的效率,算法的时间和空间哪个更好,具体选择哪种和需求有关,基本存储结构既可以单独使用,也可以组合使用。
      在这里插入图片描述

二、抽象数据类型

数据类型是指一组性质相同的值的集合及定义在该集合上的一些操作的总称。而抽象是指抽象出事物具有的普遍性的本质,它是抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。抽象隐藏了繁杂的细节,只保留实现目标所必须的信息。因此抽象数据类型可以定义为:

抽象数据类型(Abstract Data Type,ADT)是指一个数学模型及定义在该模型上的一组操作,它是一种向用例隐藏内部表示的数据类型。

面向对象编程的特征之一就是使用数据类型的实现封装数据,以简化实现、隔离用例开发、实现模块化编程。抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。它将实际生活中的问题分解为多个规模小、能够独立开发和调试的小型模块,然后进行独立编程。这种方式将代码的影响限制在局部区域,改进了我们的软件质量,促进了代码复用。抽象数据类型抽象的层次越高,那么可复用性也越强。比如:java中的Object是对所有对象的抽象。

java中数据类型可以分为两类:
在这里插入图片描述

  • 基本(原子)类型:不可以再分解的基本类型,包括int、short、long等
  • 引用(结构)类型:由其他类型组合而成,可以再分解。如,String、数组等

注意:

  1. 对原子类型的操作不一定是原子操作,这点并发编程时应特别注意。如,在32位机上对long类型的操作就不是原子操作,因为其高32位和低32位是分别存储的。
  2. Java中所有的基本数据类型都有固定的存储范围和大小,其不受具体机器和操作系统的影响。

三、算法

算法(Algorithm)一词最早出现在波斯数学家al-Khwarizmi所写的《印度数字算术》中。欧几里得算法(求两个整数的最大公约数)被认为是史上第一个算法。

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

1、算法的基本特性

  • 输入输出,算法具有零个或多个输入,至少有一个或多个输出。
  • 有穷性,算法在执行有限步后能够自动结束,不会出现无限循环。
  • 确定性,算法的每一步都具有确定的含义,不会出现二义性。
  • 可行性,算法的每一步都能够通过执行有限次操作完成。

2、程序与算法的区别

程序(program)是软件开发人员根据用户需求开发的、用程序设计语言描述的适合计算机执行的指令(语句)序列。它包括「数据结构」、「算法」、「程序设计方法」和「编程语言」。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有穷性,比如操作系统也是一种程序,它可以一直运行。

3、算法的设计要求

  • 正确性,算法至少应该具有输入、输出和加工处理无歧义、能正确反映问题的需求、能够得到问题的正确答案。
  • 可读性,便于阅读、理解和交流。
  • 健壮性,输入不合法时,算法能够给出相应的处理,而不是产生错误的结果。
  • 高效性,算法应该尽量满足高效率和低存储的需求。

四、算法的复杂度

算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。

1、时间复杂度

算法的时间复杂度反映了算法执行的时间长短,它是度量一个算法好坏的重要指标。

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

度量一个算法的时间复杂度通常有两种方式:

  • 事后统计法
  • 事前分析法(大O表示法)
    算法的时间复杂度是由最深层嵌套语句的频度决定的。

大O表示法的推导:

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的运行次数函数中,只保留最高阶
  3. 将最高阶系数变为1

例1:

int i, j, temp;
for(i=0; i<n; i++) {for(j=i, j<n; j++) {temp++;}
}

语句执行的总次数:
在这里插入图片描述

其时间复杂度为O(n^2)。

例2:

for(i=1;i<=n;i=i*2){System.out.println(i);
}

执行的总次数满足:
在这里插入图片描述

所以它的时间复杂度为O(logn)

例3:分析冒泡排序算法的时间复杂度

//冒泡排序算法
public static void bubbleSort(int[] data) {if (data == null) {return;}int temp = 0;for (int i = data.length - 1; i > 0; --i){for (int j = 0; j < i; ++j){if (data[j + 1] < data[j]){temp = data[j];data[j] = data[j + 1];data[j + 1] = temp;}}}
}

算法分析:

在这里插入图片描述

常见时间复杂度大小关系:

在这里插入图片描述

算法的时间复杂度和两个因素有关:算法中的最大嵌套循环层数;最大嵌套循环结构中每次循环的次数。一般来说,具有多项式时间复杂度的算法是可以接受的;具有指数时间复杂度的算法,只有当n足够小时才可以使用。一般效率较好的算法要控制在O(N)或者O(log2 N)

2、空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。其中,n为问题规模,f(n)为语句关于n所占存储空间的函数。

算法的空间复杂度分析方法和算法的时间复杂度分析方法基本相同。

例如:

int i, j, temp;
for(i=0; i<n; i++) {for(j=i, j<n; j++) {temp++;}
}

上方代码中,仅需为变量 i、j、temp分配空间即可,所以空间复杂度 S(n)=O(1)。

相关文章:

数据结构与算法(一):概述

数据结构学了有一年左右的时间了&#xff0c;但是一直没有详细地总结一下&#xff0c;现在回想起来&#xff0c;感觉有些内容忘记了。所以接下来一段时间我将重新归纳总结一下&#xff0c;算是温故而知新了。 一、数据结构 1、定义 数据结构是计算机存储、组织数据的方式。在…...

Spring3之Bean的属性详解

简介 Spring 中大量使用到 Bean 的注入来实现各个模块之间的依赖&#xff0c;本章将详细介绍 Bean 的主要属性 id 和 name 属性 每个 Bean 可以有一个 id 属性&#xff0c;并可以根据该 id 在 IoC 容器中查找该 Bean&#xff0c;该 id 属性值必须在IoC 容器中唯一 可以不指定…...

C语言之结构体内存的计算

结构体的内存 一.提出疑问 结构体占用的是一片连续的内存空间&#xff0c;大小是由成员变量的类型决定的。但并不是计算所有成员变量的类型大小之和那么简单。 先举一个实例&#xff1a; struct student {int age; //4个字节int telephone; //4个字节 }; int main() {struc…...

Java网络编程之UDP和TCP套接字

文章目录一. 网络编程概述二. UDP网络编程1. UDP套接字2. UDP客户端回显服务器程序2.1 UDP回显服务器2.2 UDP客户端2.3 UDP实现查词典的服务器三. TCP网络编程1. TCP套接字2. TCP客户端回显服务器程序2.1 TCP回显服务器2.2 TCP客户端2.3 解决服务器无法同时出力多个客户端的问题…...

Linux进程信号产生以及捕捉

一.什么是信号 生活中&#xff0c;有哪些信号相关的场景呢&#xff0c;比如&#xff1a;红绿灯&#xff0c;闹钟&#xff0c;转向灯等等 1.这里我们要知道&#xff0c;你为什么认识这些信号呢&#xff0c;记住了对应场景下的信号&#xff0b;后续是有”动作“要你执行的 2.我们…...

11. GLSL(OpenGL Shader Language)常用知识点汇总

1. 说明&#xff1a; 在使用OPenGL进行三维模型渲染时&#xff0c;需要使用到两个着色器对模型进行位置设置和颜色设置&#xff0c;分别为顶点着色器和片段着色器&#xff0c;这两个着色器是使用 GLSL 语法进行编写的。这篇文章总结了一些GLSL中的一些基本语法知识。 2. 基本…...

转发一张网络工程师考试的试卷2021.5.15

网络工程师考试 单选题 &#xff08;30题&#xff0c;每题1分&#xff0c;共30分&#xff09; 1. 你在一个网络中实现DHCP服务&#xff0c;配置一些计算机成为DHCP客户端&#xff0c;由于工作需要&#xff0c;一台系统为Windows 10 的客户端要把从DHCP服务器获得的地址释放&a…...

AMD发布23.2.1 新驱动 支持开年新作《魔咒之地》

如果说2023年有什么新作&#xff0c;《魔咒之地&#xff08;Forspoken&#xff09;》当属开年大作之一&#xff0c;1月25日才在steam平台发售。虽然开售后的表现似乎不如想象中优秀&#xff0c;加之价格相对昂贵&#xff0c;令不少玩家望而却步&#xff0c;但如果只是想尝鲜&am…...

开放平台如何做接口的签名和加解密?

目录安全性功能介绍实现流程开放平台依赖代码AES加解密工具类PlatformConfigRequestUtilsPlatformServiceCommonCodeZuulFilterHelperServerResponsePlatformContactRsaSignatureRsaUtilsStreamUtil开放平台-解密过滤器开放平台-加密过滤器调用方代码公共代码Get-DemoPost-Demo…...

Mr. Cappuccino的第40杯咖啡——Kubernetes之Pod生命周期

Kubernetes之Pod生命周期Pod生命周期官方文档Pod的状态初始化容器案例钩子函数Exec命令TCPSocketHTTPGet案例容器探测Exec命令TCPSocketHTTPGet探测时间重启策略Pod生命周期官方文档 Pod生命周期官方文档 Pod的状态 pending&#xff1a;挂起&#xff0c;apiserver创建了pod资…...

记一次OOM

1,问题描述&#xff1a; 新上了一版代码之后&#xff0c;上游服务请求我们服务失败&#xff0c;报错&#xff1a;“服务不可用”&#xff0c;发现注册中心上服务掉线&#xff0c;查询日志&#xff1a;发现oom&#xff1a;Java heap space,GC overhead limit exceeded。 容易…...

idea插件生成dao类service类controller类以及mapper.xml

idea插件生成dao类service类controller类以及mapper.xml 安装插件Easycode和MybatisX&#xff0c;不用自己写代码 1.Files——》Settings——》Plugins&#xff0c;分别搜索Easycode和MybatisX&#xff0c;点击下载。 2.新建一个springboot模板&#xff0c;选择的依赖如下 3.…...

DML 数据操作语言

概述 DML英文全称是Data Manipulation Language(数据操作语言)&#xff0c;用来对数据库中表的数据记录进行增、删、改操作。 添加数据&#xff08;INSERT&#xff09;修改数据&#xff08;UPDATE&#xff09;删除数据&#xff08;DELETE&#xff09; 添加数据 1、给指定字段…...

PySpark实战一之入门

1、PySpark的编程模型 分三个模块&#xff1a; 数据输入&#xff1a;通过SparkContext对象&#xff0c;完成数据输入 数据处理计算&#xff1a;输入数据后得到RDD对象&#xff0c;对RDD对象的成员方法进行迭代计算 数据输出&#xff1a;最后通过RDD对象的成员方法&#xff0…...

【DockerCE】Docker-CE 23.0.1正式版发布

很意外啊&#xff01;Docker社区版竟然直接从20.xx.xx版本&#xff0c;升级到23.xx.xx版本了。官网地址&#xff08;For RHEL/CentOS 7.9&#xff09;&#xff1a;https://download.docker.com/linux/centos/7/x86_64/stable/Packages/23.0.1版本官方安装包如下&#xff1a;# l…...

vscode开发的Vue家用电器维修服务系统nodejs+mysql

主要功能包括管理员&#xff1a;首页、个人中心、用户管理、维修员管理、维修信息管理、维修申请管理、维修处理管理、家电类别管理、配件信息管理、配件领用管理、维修结果管理、家电维修知识管理、公告信息管理、留言板管理&#xff0c;用户&#xff1a;首页、个人中心、维修…...

PyQt5数据库开发1 4.2 配置SQL Server 2008 数据源(ODBC编程)

文章目录 配置SQL Server 2008 数据源&#xff08;ODBC编程&#xff09; 1. 了解要配置的数据源服务器名称&#xff0c;以及数据库和对应表 2. 打开控制面板&#xff0c;点击管理工具 3. 双击数据源 4. 选择“用户DSN”选项卡&#xff0c;点击“添加” 5. 选择SQL Serv…...

【JavaEE】多线程代码实例:单例模式与阻塞队列BlockingQueue

目录 单例模式&#xff1a; 什么是单例模式&#xff1f; 单例模式的实现方式&#xff1a; 饿汉模式&#xff1a; 懒汉模式&#xff1a; 基于并发编程对单例模式线程安全问题的讨论&#xff1a; 阻塞队列&#xff1a; 标准库中的阻塞队列&#xff1a; 自实现阻塞…...

算法思想 - 搜索算法

本文主要介绍算法中搜索算法的思想&#xff0c;主要包含BFS&#xff0c;DFS。搜索相关题目深度优先搜索和广度优先搜索广泛运用于树和图中&#xff0c;但是它们的应用远远不止如此。BFS广度优先搜索的搜索过程有点像一层一层地进行遍历&#xff0c;每层遍历都以上一层遍历的结果…...

C#底层库--日期扩展类(上周、本周、明年、前年等)

系列文章 C#底层库–记录日志帮助类 本文链接&#xff1a;https://blog.csdn.net/youcheng_ge/article/details/124187709 C#底层库–数据库访问帮助类&#xff08;MySQL版&#xff09; 本文链接&#xff1a;https://blog.csdn.net/youcheng_ge/article/details/126886379 …...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...