数据结构初阶

这篇具有很好参考价值的文章主要介绍了数据结构初阶。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

基本概念和术语

讲到了数据结构是什么,我们就得先知道什么叫做数据。

数据

  数据,《大话数据结构》这本书中,给出的定义:是描述客观事物的符号,是计算机中可以操作的对象,是能够被计算机识别,并输入给计算机处理的符号集合。

  数据不仅仅包括整型,实型等数值类型,还包括字符及声音,图像,视频等非数值类型。

数据结构与数据库的区别

首先,我们先要区别开两个概念,这两个概念分别是什么呢?

分别是数据结构和数据库。这两个都是对数据进行管理,但他们的区别呢:数据结构是在内存中管理数据,而数据库呢是在磁盘中管理数据。

两个管理数据分别有着各自的好处:数据结构呢是速度快,但是需要带电存储。

而数据库呢是在磁盘中管理数据,相对于数据结构在内存中管理数据它的速度较慢,但是可以不带电存储。

算法

算法定义

什么是算法呢?

我们继续看《大话数据结构》这本书中,书中给中的解释是算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

我认为我们可以简单理解一下算法,其实就是解决问题的方法,在生活中,我们会遇到各种各样的问题,算法呢,可以说是我们解决问题的途径。

比如,在大学生活的我们,刚刚到月中,但是我们的生活费却没有了,这是我们现在所遇到的问题,针对于这个问题,我们就得想出我们的解决办法了。我们可以有好几种解决办法。

比如:

1.我们去向父母寻求支援。

2.我们可以向朋友请求支援。

3.我们可以去打工,做兼职,去挣取我们的生活费。

算法定义中,得到了指令,指令能被人或者机器等计算机装置执行。为了解决某个或者某类的问题,需要把指令表示成一定的操作序列,操作序列包括一组操作,每一个操作都能完成特定的功能。

在这个问题中,我们看到了三种解决方法,而这三种方法一步步可以当成指令,我们按照指令一步步运行起来,我们就可以得以解决我们所需要面对的文问题。

上述我们提出的三个问题进一步细分成我们一步步的步骤,然后我们完成操作,达成功能。这就是算法。

算法的特性

算法具有五个特性,分别是输入、输出,有穷性、确定性和可行性。

有穷性。一个算法必须总在执行有穷步之后结束,且每一步都可以在有穷时间内完成。

确定性。算法中每条指令必须有明确的含义。对于相同的输入只能得出相同的输出。

可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

输入。一个算法有零个或者多个输入,这些输入取自于某个特定的对象的集合。(这一条不是很准确的理解,自我感觉是对于输入数据的定义嘛?比如 int a = 0;这种对于a变量的类型的锁定,使其在int整型集合中吗?)

输出。一个算法有一个或者多个输出,这些输入取自于某个特定的对象的集合。

针对于解决问题的算法,应该考虑达到以下目标。

1.正确性。算法应该能够正确地解决求解的问题.

2.可读性。算法应该具有良好的可读性,让人们可以方便理解。

3.健壮性。输入非法数据时,算法能适当地做出反应或者进行处理。而不会产生莫名其妙的输出结果。

4.高效率性和低存储量需求。效率是指算法执行的时间,存储量需求是指算法执行过程中所需要的最大存储空间。这两者都与问题的规模有关。

在效率与存储空间的要求下,我们当然愿意选择效率高的和低存储空间的算法,可是我们又该怎么对这两个东西比较呢。所以我们引出了时间复杂度和空间复杂度的定义。

时间复杂度

时间复杂度的定义

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。

一个算法执行所消耗的时间,从理论上来说是不能算出来的,只有你把你的程序放在机器上跑起来才能知道。但是我们如果每个算法都上机测试,这是很麻烦的一件事情。

所以才有了时间复杂度这个分析方式,它是一个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例。

算法中的基本操作的执行次数,为算法的时间复杂度。

即:找到某一条基本语句与问题规模N之间的数学表达式。就是算出了该算法的时间复杂度/。

数据结构初阶,数据结构

我们从一个相对简单的例题引入我们的时间复杂度的计算。

从上面我们得知,我们需要某条基本语句与问题规模N之间的数学表达式,从上面这个例题,我们进行分析

,第一个循环语句进行N次,然后在它里面的循环语句,也进行了N次,所以外层循环加内层循环总共进行了N的平方次,然后再将下面的循环语句进行累加,和最下面的while循环循环次数10进行累加,我们得知F(N)=N*N+2N+10;

经过上述分析,我们就可以得出这个的时间复杂度是这个上面的表达式,但因为我们在计算时间复杂度时候通常是进行的大约计数,所以我们在进行时间的复杂度的计算时,通常采用:

大O的渐进表示法

推导大O阶的方法:

1.用常数1取代运行时间中的所有加法常数。

2.在修改后的运行次数函数中,只保留最高阶项。取决定性的那一项,即上方例子中的N*N这一项。

3.如果最高阶项存在且不是1,则去除掉与这个项目相乘的常数。得到的结果的就是大O阶。

最好,最坏,和平均。取最坏的O (N)

时间复杂度的计算估算是保守的估算

数据结构初阶,数据结构

在实际中,我们一般关注的是算法的最坏运行情况。所以在这个情境下的时间复杂度我们是O(N)。

  我们下面来关注一下这个例题,从中我们看出循环的次数是一个常数。我们将这个算法的时间复杂度记成O(1).它中间代表的1代表的意思不是一次,而是常数次。我们需要多加区分,因为在现在cpu运行条件下,常数次的运算情况并不会让我们在感觉上产生太大的感觉。

数据结构初阶,数据结构

     时间复杂度计算不能数代码中的循环,要根据思想,灵活计算。数据结构初阶,数据结构

我们将视角先看到这张图的左边,这个冒泡排序的时间复杂度是多少呢,是O(N*N),有的同学是怎么计算的呢,是数它的算法中有两层循环,两次循环就粗略的认为是O(N*N)了,这样的理解是错误的。

我们将视角投向到右边那个代码中,右边那个代码的时间复杂度是你想象中的那个样子嘛?
不对,它的时间复杂度是O(N)。

为什么会是这样呢,这是我们后续需要学习的一个排序方法,假设我们第一数是5,我们就将这个5设置成了一个keyi,然后右边给了一个right,左边给了一个left,如果我们右边的right大于keyii,我们就将right--,这是一个找小过程,而左边的left同样的道理,它是一个找大的过程然后。从代码中看,right和left走走走,最后会在途中的某个地方相遇,然后一边是比keyi大的,一边是比keyi小的数。

这样我们时间复杂度大家就可以说出来了吧,因为它总共才遍历了一遍这个数组,所以它的时间复杂度是O(N)。

如果有什么错误,请大家多多指正,我也会在学习了新的知识后,对旧的知识进行更新与反思。希望大家多多支持。有错误也请麻烦大家多多指正。文章来源地址https://www.toymoban.com/news/detail-763989.html

到了这里,关于数据结构初阶的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构初阶--二叉树的链式结构

    目录 一.二叉树链式结构的概念 二.二叉树链式结构的功能实现 2.1.链式二叉树的定义 2.2.链式二叉树的构建 2.3.链式二叉树的遍历 2.3.1.先序遍历 2.3.2.中序遍历 2.3.3.后序遍历 2.3.4.层序遍历 2.4.链式二叉树的求二叉树的结点数量 法一:计数法 法二:分治法 2.5.链式二叉树的求二

    2024年02月12日
    浏览(43)
  • 初阶数据结构:顺序表

    了解到学习数据结构与算法的重要性后,又学习了评判程序效率高低算法好坏的标准,时间空间复杂度。接下来,进行一些简单数据结构的初步学习。所有数据结构中存在着可以划分为一大类的简单结构, 线性表 ,即在 逻辑上都呈现线性关系 的数据结构(物理结构上不一定

    2024年01月20日
    浏览(50)
  • [数据结构初阶]双链表

    目录 双链表定义 初始化 创建节点  尾插 ​编辑 尾删 头插 头删 打印 查找 pos插入 头插复用 尾插复用  pos删除 头删复用 尾删复用 判空 size 销毁  完整代码 前面我们学习了单链表,但按照 带头不带头(哨兵)和循环不循环 我们可以有四种单链表,双链表也是如此,我们最常

    2024年02月12日
    浏览(38)
  • 【数据结构初阶】顺序表

    线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月02日
    浏览(47)
  • 数据结构初阶--排序2

    本篇文章将继续介绍快排,归并等排序算法以及其变式。 快速排序是Hoare于1962年提出的一种 二叉树结构 的交换排序方法。 其基本思想为:任取待排序元素序列中的某元素作为 基准值 ,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序

    2024年02月16日
    浏览(36)
  • 【数据结构初阶】双链表

    1.1结口实现 1.2申请结点 1.3初始化双链表 1.4打印双链表 1.5尾插 1.6尾删 1.7头插 1.8头删 1.9计算大小 1.10查找 1.11pos位置插入 1.12删除pos位置 1.12删除双链表 List.h List.c test.c 💘不知不觉,【数据结构初阶】双链表 以告一段落。通读全文的你肯定收获满满,让我们继续为数据结构学

    2024年02月05日
    浏览(40)
  • 初阶数据结构(三)链表

    💓博主csdn个人主页:小小unicorn💓 ⏩专栏分类:c++ 🚚代码仓库:小小unicorn的学习足迹🚚 🌹🌹🌹关注我带你学习编程知识 前面我们讲的线性表的 顺序存储结构 。它是有缺点的,最大的缺点就是插入和删除时需要移动大量元素,这显然就需要 耗费时间 ,那能不能想办法

    2024年02月09日
    浏览(61)
  • C语言完整版笔记(初阶,进阶,深刨,初阶数据结构)

    1.初阶: 1.1C语言初阶易忘知识点速记 2.进阶:  1.2C语言进阶易忘点速记 3.深剖: 2.1C语言重点解剖要点速记 2.2C语言重点解剖操作符要点速记   2.3C语言重点解剖预处理要点速记 2.4C语言重点解剖指针和数组要点速记 2.5C语言重点解剖内存管理函数要点速记 4.数据结构:

    2024年02月16日
    浏览(38)
  • 【数据结构初阶】链表OJ

    OJ 方案一: 题目解析: 方案二: 题目解析:把原链表遍历一遍,插入新链表 OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: 定义快慢指针,使快指针先走与慢指针同步。然后同时走看是否相交 OJ 题目解析: OJ 题目解析:

    2024年02月05日
    浏览(51)
  • 数据结构(初阶)第二节:顺序表

    数据结构(初阶)第一节:数据结构概论-CSDN博客 从本文正式进入对数据结构的讲解,开始前友友们要有C语言的基础,熟练掌握 动态内存管理 、 结构体 、 指针 等章节,方便后续的学习。 顺序表(Sequence List) 顺序表的分类 静态顺序表 动态顺序表 顺序表的功能 初始化 扩

    2024年04月12日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包