(数据结构)第一章 绪论

news/2024/4/16 21:53:59

1.1 计算机与算法

1.1.1 计算

计算首先是我们这门课程的直接研究对象和内容,也是我们这门课程的研究目的和目标。

对象:规律、一般性方法、技巧

目标:高效计算、低耗

  • 绳索计算机

要求:通过直线l上给定的点A,作该直线的垂线。

过程:

计算机:长度为12 的绳索。

计算:重复机械的完成以上的过程。

  • 尺规计算机

输入:任给平面上线段AB

输出:将其三等分的C和D点。

算法:

 

1.1.2 什么是算法?

计算=信息处理

借助某种工具,遵照一定规则,以明确而机械的形式进行

计算模型=计算机=信息处理工具

基于特定的计算模型,解决某一信息处理问题而设计的一个指令序列。

  • 算法具备的要素:
  1. 输入:待处理的信息(问题)
  2. 输出:经处理的信息(答案)
  3. 正确性:的确可以解决指定的问题
  4. 确定性:任一算法都可以描述为一个由基本操作组成的序列
  5. 有穷性:对于任何输入,经有穷次基本操作,都可以得到输出
  6. 可行性:每一基本操作都可以实现,且在常数时间内完成

例如:如何把大象装进冰箱?

但是有一条是不能实现的:把大象赶进冰箱里面

1.1.3 有穷性

针对Hailstone sequence问题,详细介绍算法的有穷性。问题如下:

对于任何一个自然数都可以定义这样的序列:以递归的形式定义,实例如下:

 

 以上这个程序未必是一个算法:无法证明其是有穷的。

补充:序列有时会下降有时会上升,虽然有可能持续下降,但是绝不会持续上升,原因是一个奇数乘3加1之后会成为偶数,再进行折半,而不会连续乘3加1。

程序未必是算法。程序如果要称作是一个算法,它就应该满足我们刚刚说过的有穷性。它对任何的输入,都应该能够在有限步之后退出返回。该程序对任何n都能做到这一点吗?这不取决于这个程序,而是取决于这个序列本身的定义。目前,这个问题还没有结论。

  • 我们应该考虑的问题:
  1. 什么是好的算法?
  2. 什么是好的数据结构?
  3. 什么是好的计算过程?

算法:需要考虑如何设计、优化?

优劣:如何评判和比较好的算法?

1.1.4 好算法

正确:符合语法,能够编译、连接

  • 正确处理简单输入
  • 正确处理大规模输入
  • 正确处理一般性的输入
  • 正确处理退化的输入
  • 正确处理任意合法的输入

健壮:能辨别不合法的输入并做适当处理,而不致非正常推出

可读:结构化+准确命名+注释+

效率(最重要):速度尽可能快,存储空间尽可能少

Algorithm + Data Structures = Programs

(Algorithm + Data Structures)× Efficiency = Computation

1.1.5 复杂度的度量

算法分析:主要体现在两个方面

正确性:算法功能与问题要求是否一致

成本:运行时间 + 所需存储空间

  • 特定算法+特定实例

定义:T_{A}(P)=算法A求解问题实例P的计算成本

结论:问题实例的规模,往往是决定计算成本的主要因素

通常:规模接近,计算成本接近;规模扩大,计算成本也上升

  • 特定算法+不同实例

T_{A}(n)=用算法A求解某一问题规模为n 的实例(一类问题),所需的计算成本。讨论特定算法A(及对应的问题)时,简记T(n)

观察:同一问题等规模的不同实例,计算成本不尽相同,甚至有是指差别。

  • 特定问题+不同算法

同一问题通常有多种算法,如何评价其优劣?

最直接:实验统计,实际中不能足以反应算法的真正效率

可行方法:抽象出一个理想的平台或模型,不再依赖于具体的因素,从而直接而准确地描述,测量并评价算法。构建理想的平台或模型。

1.1.6 什么是图灵机?

图灵机模型具有以下要件:

Tape也就是带:通常称作纸带或磁带,被均匀地划分为一个一个的小格子,称作cell。每一个小格子上面都标注有某个字符,默认的初始情况下 所有的格子中都标记有一个特定的符号,比如说我们这里约定是“﹟”号,所以相应的每个格中所标的字符,都是来自于一个字符表。而这个字符表的长度是有限的。

Head:头。在任何时刻Head,都是对准了Tape上的某一个cell,而整个的图灵机,按照一个节拍的节奏来运转,每经过一个节拍,这个头都可以向左或者是向右移动一个单元,转入下一个单元格。而在对准任何一个单元格的时候它都可以读取出这个单元格中所标注的那个字符。也可以修改这个单元格中所对应的字符。正因为这个原因,它确实应该叫作读写头

具有两方面的功能:读和写。

State :TM总是处于有限种状态中的某一种,每经过一个节拍,可(按照规则)转向另一个状态

规则:Transition Function:(q, c ; d, L/R, p)若当前状态为q且当前字符为c,则当前字符改写为d;转向左侧/右侧的领格;转入p状态,一旦转入特定的状态‘h',则停机,计算任务完成。

实例:

如何利用图灵机来完成非负整数加1的功能?

约定:非负整数统一以二进制形式在纸带上用若干个单元表示。

要点:在其中的这样一个比特,从右向左,从最低位向更高位数,所能发现的第一个零比特。那么它后面那些比特都应该是1。我们要完成这项工作,实际上只需做这么样一件事,就是将这个比特后续的所有那些1 翻转为零。而原先最低位的这个零翻转为1。如下图所示。

转换过程:初始是向左状态,所对的字符是1,应该翻转为零,向左侧移动一步,继续保持原来的向左的状态。概括而言,扫描作为最低位那个零的,后缀的那些1比特将它们逐个的翻转为零,在这个过程中,保持图灵机向左的状态。如果我们终于不再碰到的是1,第一次碰到零,将这个零翻转为1。读写头开始向右。在此之前,原来的那些1比特都已经转化为了相应的零比特。将读写头完整的送回原来的位置,并停机。

为什么要把读写头复位到最初的位置?

规范,它有可能本身以后会成为一个算法的一部分,而那个算法在每次调用使用它之前,都会对它当时所处的整体状态,有一个严格的规范要求。

1.1.7 RAM模型

在可计算的意义上讲,它和图灵机是完全对等的,二者之间的一个共同之处是他们拥有无限的空间,当然在实际世界中还不能做到。每一个寄存器,都由一个自然数唯一的标识。这里提供了一系列的可行的语句。例如,常数赋值语句;把第j个寄存器中的数值赋值到第i个寄存器中,条件判断语句等。

图灵机与RAM模型都是对计算工具进行抽象以后的简化,不仅可以用这种基本的简单的操作描述我们的算法,而且独立于具体的环境和平台,对具体算法的总体效率做出比较和评判,相对于前面那种实测的方法,更具可信度。

关键:时间\rightarrow次数。将算法所运行的时间转化为在上述这些基本平台上执行算法的过程中所需执行基本操作的次数

该方法的优点:可以不用考虑硬件环境,一个算法好不好并不取决于运行的时候所依赖的那个CPU主频的快慢,而取决于它本身它需要执行多少次CPU的计算。

实例:

算法功能:在向下取整的意义上的除法,具体来说,对于任何一个非负整数c,和正整数d 我们都需要在做完除法之后,再实施向下取整得到一个整数。那么这个输出,实际上也就是不超过c/d的那个最大整数。

算法如下:

执行过程可以记录为一张表,表的行数即是所执行基本指令的总条数。

总结:这张表所暗示的,不光可以把整个计算过程逐次罗列出来,更重要的是将整个计算过程所需要的计算成本,转化为了这个表的规模或者说它的高度(表的行数)。执行的基本操作的次数实际上就是这个算法所需时间的一个最客观的度量。

目标:是给出一个清晰的尺度,用来对算法进行度量,可以此判断哪个算法的性能更好。尺子怎么用,需要继续学习下面的内容。

 

1.2 复杂度度量

 

1.2.1 渐进分析

渐进分析:关心足够大的问题,注重考察成本的增长趋势。

问题:在问题足够大之后,计算成本如何增长?  运行时间 + 所需存储空间

  • 大O记号:T(n)的上界

存在正常数c和函数f(n)对任何n>>2都有

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


http://www.ppmy.cn/news/915921.html

相关文章

JavaWeb — 系统结构分析

目录 总体学习内容 Servlet 关于系统架构 B/S结构的系统通信原理(没有涉及到Java小程序) 关于WEB服务器软件 解决Tomcat服务器在DOS命令窗口中的乱码问题(控制台乱码) 实现一个最基本的web应用(这个web应用中没有…

数据结构知识详解 第一章 绪论

知识框架 1. 数据结构的基本概念 1.1 基本概念和术语 1.1.1 数据 定义:是信息的载体,是描述客观事实属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合 数据的组成: 整型、实型等数值类型字符及声音、图像、视频等…

java学习笔记,面向对象和对象的内存结构

一、概述 面向对象是基于面向过程的编程思想。 二、特点 是一种更符合我们思想习惯的思想可以将复杂的事情简单化将我们从执行者变成了指挥者 三、特征 封装继承多态 四、类与对象 类:是一组相关的属性和行为的集合对象:是该类事物的具体体现 五…

我们到底该如何学习《数据结构与算法》?

本文出自《愚公要移山》个人博客中,地址www.javachat.cc 收录于《手牵手一起学习数据结构与算法》专栏 前言:我们到底该不该学习算法与数据结构? 1、真的应该学习 这个问题本身就不是个问题,所有人都在强调数据结构与算法比较重要,但是好像平时也没用到,无法直观的去感受…

算法---数据结构

数据结构 数据之间的相互关系称为逻辑结构。通常分为四类基本结构: 集合 结构中的数据元素除了同属于一种类型外,别无其它关系。 线性结构 结构中的数据元素之间存在一对一的关系。 树型结构 结构中的数据元素之间存在一对多的关系。 …

《数据结构与算法之美》学习汇总

此篇文章是对自己学习这门课程的一个总结和课后的一些练习,做一个汇总,希望对大家有帮助。本人是半路程序员,2018年2月开始学习C的,下面的代码基本都是C11版本的,代码有错误的地方请不吝留言赐教。附有部分练习LeetCod…

python做路径图_初学者福利:python路线图

原标题:初学者福利:python路线图 编程思维简单地分成了两个主要部分,一个是建模,一个是算法优化。 举个例子,比如我们想要做一个程序,这个程序会自动把大象装进冰箱里。那么建模是什么呢?就是我…

一班洽谈框架细化_细化结构图让文章结构更清晰 邱晓风

细化结构图让文章结构更清晰 梨园镇中心小学 邱晓风 语文教学中提倡引导学生从整体入手,再部分感知,最后再回归整体,这样才能够使学生从整体到部分再到整体的感知课文,真正地从多角度了解文章内容,感知文章的叙述手法&…

【产品经理入门】规划5-流程图与结构图

**实现目标** 熟悉流程图常见类型 熟悉绘制流程图时的组成元素 进行流程图绘制 了解产品结构图画法一、流程图类型 1 流程定义: 为了达到某种目标而进行的一系列有逻辑的操作步骤,由两个及以上的步骤,完成一个完整的行为的过程,…

mysql 用户表结构设计_MySQL数据表结构设计

1表结构 每个表的内容: image image image image image image image image 2表关系 天蓝色代表表中有唯一索引。

Java的基础理论知识(程序设计以及结构图)

Java基础 1、 简述Java的基本历史 java起源于SUN公司的一个GREEN的项目,其原先目的是:为家用消费电子产品发送一个信息的分布式代码系统,通过发送信息控制电视机、冰箱等 2、 简单写出Java特点,写出5个以上,越多越好…

python程序中的组织结构

目录​​​​​​​ 顺序结构 对象的布尔值: 选择结构 单分支结构 双分支结构 多分支结构 嵌套if 条件表达式 pass语句 range()函数 循环结构 while循环语法结构: for-in循环 break语句 continue语句 else语句 嵌套循环 顺序结构 程序从上到下顺序的…

数据结构作业之栈递归

递归 程序调用自身的编程技巧称为递归( recursion)。递归作为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来…

顺序存储结构的线性表

1.0. 什么是线性表? 所谓线性,即一条线,这条线可以是直线,也可以是曲线。 所谓表,肯定都不陌生,生活中有各种各样的表或者表格。我们在表格中填写各种各样的信息,通过表格,能够很好…

java汉诺塔图解,用把大象放进冰箱理解汉诺图

了解递归先从一个通俗例子开始 举一个通俗的例子: 有一个800g重的苹果要你切成重量相等的若干份,每一份的重量不能大于100g。你肯定会想到这样做: 1.第一刀先把一个苹果切成重量均等的2份A1和A2; 2.再把其中的一份A1切成重量均等…

深度学习网络结构图

深度学习初探——入门DL主流框架 作者 实验楼 关注 2017.03.09 14:30 字数 2541 阅读 3294 评论 0 喜欢 2 深度学习概念 深度学习 (deep learning):深度学习是机器学习中的一个分支,试图通过具有多个处理层的计算模型对数据进行多层抽象。这个抽象的结果…

python绘制组织结构图_二、Python的程序组织结构

1.顺序结构 注:计算机的流程控制:顺序结构、选择结构、循环结构 程序从上向下执行,直到结束. print(------程序开始------) print(1.把冰箱门打开) print(2.把大象放在冰箱里) print(3.把冰箱门关上) print(------程序结束------) 结果&#…

无重复字符的最长子串

无重复字符的最长子串 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: s “bbbbb” 输出: 1 解释: 因为无重…

云原生|kubernetes|kubernetes集群部署神器kubekey的初步使用(centos7下的kubekey使用)

前言: kubernetes集群的安装部署是学习kubernetes所需要面对的第一个难关,确实是非常不好部署的,尤其是二进制方式,虽然有minikube,kubeadm大大的简化了kubernetes的部署难度,那么,针对我们的学习环境或者…

7月9日逆战服务器维护多长时间,逆战7月9日更新内容

逆战7月9日更新内容分享给大家,这次的更新可是新版本的更新哦,更有礼包上线哦,大家可别错过了,那么下面就赶紧和小编一起去看看具体内容吧。 尊敬的逆战玩家: 为了给各位玩家带来更优质的游戏体验,我们将于…
最新文章