专栏首页java_python算法初步---基本的数据结构(java为例)

算法初步---基本的数据结构(java为例)

  最近搞算法,觉得超级吃力的,一直以为数学好的,数学可以考试满分,算法一定没什么问题,贱贱地,我发现我自己想多了,还是自己的基础薄弱吧,今天我来补补最基础的知识。

  算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

  最简单的栗子,我们来计算1+2+3+4+...+100,我们逐个去算觉得好麻烦的。如果是加到200呢?加到500呢?这时就引出了我们的算法,高中数学就说过这个玩意,等差数列,也就是Sn=a1*n+[n*(n-1)*d]/2,我们带入公式来看一下。Sn = 1*100+ [(100*99)/2]

5050,应该和我们一个个来计算一样的吧。这个简单的栗子也就是我们的算法(现实中没有这么简单的),但从这个简单的栗子我们可以得到我给们要给予100个数字,我们就要计算100次,给出101个数字就要计算101次,那么我们给出n给数字也就是要计算n次啦

所以我们就说我们的时间复杂度为O(n)。这次我们又假如,我们去吃小龙虾,我们吃掉第一只小龙虾需要1分钟,吃第二只需要两分钟,吃第三只时候需要三分钟,那么我们吃掉n只龙虾需要多久呢?我们根据推算可以知道,我们需要 (n2+n)/2。时间复杂度即为O(n

2)

  这时我们也就得到了时间复杂度为,保留最高阶,常数变为1的结论,去得出时间复杂度。

  空间复杂度,也就是占用内存的大写啦,多次循环的时候,其实一直占用内存的,一直没有释放的,只要指针还在,我们的内存就没有释放的。一般也用O(n)来表示,运行几次就是几啦,记得把变量算进去。

  说好的说数据结构,提前说了时间复杂度和空间复杂度,其实没有提前,说了这两个概念,后面的很多也就很好理解了。

  线型结构:数组和链表。

数组:

  数组就像是训练有素的士兵一样,报数1,2,3....我们可以通过他们的角标,得到他们的值,在java里的代表就是array啦。(在这里说一下,数据的操作一般都是增删改查,我们干过web的都知道啦)

  增:如果是尾部插入,直接给予新的角标,给予值就可以了,头部新增,需要把所有元素向后移动,中间插入也是如此的,在这里简单的说一下扩容,数组的每次扩容的2倍的,例如我们第一次占用4个单位,不够用了,我们需要扩容,直接扩展到8位(即使用不完8位,也扩容到8位)时间复杂度O(n)。

  删:删除也是如此,每次是需要移动剩余元素的,时间复杂度即为O(n)

  改:直接去改就可以啦,时间复杂度为O(1)

  查:刚才我们说了,数组是有角标的,我们直接通过角标就可以得到他们了,所以时间复杂度为O(1)

说了这些我们得到了数组的查询表现还是很好的。

链表:

  刚才说的数组像士兵一样,有着整齐的队伍,那么链表就像是地下党一样,只是单线联系,我只是知道我的下级是谁,不知道我们的组织里其他人。只是通过他们的next指针去得到下一项。

  增:在这里链表新增就简单很多了,只要找到自己要放置的位置,把指针指向他,他的指针指向他的下级就可以了,也就是说时间复杂度为O(1)

  删:删除也是如此的,我们删掉了自己,把原来指向自己的指针调整到指向我们指针原来指向的位置就可以了,时间复杂度为O(1)

  改:我们这里提要的修改,都是指不考虑查过程消耗的所有,也就是我们找到直接改就可以啦,时间复杂度为O(n)

  查:我们需要从大哥找起,问他你的下线是谁?不是我们要的,我们继续询问他的下级,所以时间复杂度为O(n)

---------------------华丽的分割线-------------------------

栈:

  栈?可以理解为羽毛球桶吧。我们依次把每一个不同颜色的羽毛球装在桶内,但是我们每次只能拿出最外面的那个羽毛球,也就是说,栈,后进先出。

  这里的栈主要操作就是入栈和出栈了,我们刚才也说了后劲先出,也就是说入栈和出栈只会影响到最后一个元素,不涉及其它元素的整体移动,时间复杂度为O(1)

队列:

  队列就犹如隧道一样吧,或者理解为二极管,只能单向通电,也就是只能单向通过,我们也就可以得知,队列的数据一定是先进先出啦。

  入队和出队,性质和栈基本都是一致的,唯一的就是先进先出。

  队列其实还有双向队列(可以两头操作)和优先队列(自带VIP光环)。

---------------------华丽的分割线-------------------------  

哈希结构:(散列表)

  哈希?可以理解为坐卧铺火车吧,上车了(开始存),列车员会把我们的票换成他们的票(哈希函数执行),然后我们会到我们相应的铺位,等待下车。也就是key,value的形式来存的,java带表示HashMap,(jdk1.8里HashMap有新特性,以后会讲到)

  新增:总共分两步,换票,上卧铺。也就是我们拿到key值进行hash计算,然后得到所对应的的位置,存储我们的值。

有时候会出现hash冲突的情况,我们一般用开放寻址和链表来解决冲突,如果太多了,会扩容,和数组扩容性质差不多,也是2倍的扩容。

  查:通过hash函数将key哈希过来,得到位置,找到我们的值,冲突了,会找他的链表。

结构我们今天先说这些,貌似这些应该是结构基础的所有了吧。有遗漏的小伙伴可以提醒我一下,我不知道的,我去学习一下,再整理发给大家。晚安。

最近搞了一个个人公众号,会每天更新一篇原创博文,java,python,自然语言处理相关的知识有兴趣的小伙伴可以关注一下。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • java架构之路-(二)Mysql索引和查询引擎

      今天我们来说一下我们的mysql,个人认为现在的mysql能做到很好的优化处理,不比收费的oracle差,而且mysql确实好用。

    小菜的不能再菜
  • java架构之路-(mybatis源码)mybatis执行流程源码解析

      这次我们来说说Mybatis的源码,这里只说执行的流程,内部细节太多了,这里只能授之以渔了。还是最近的那段代码,我们来回顾一下。

    小菜的不能再菜
  • java架构之路-(Redis专题)Redis的高性能和持久化

      上次我们简单的说了一下我们的redis的安装和使用,这次我们来说说redis为什么那么快和持久化数据

    小菜的不能再菜
  • Robot-机器人零空间问题solution

    经常在一些大牛的算法中会看到“零空间”的概念,零空间是不是与动漫中的“异次元空间”类似尼,答案是显然不是。机器人的零空间是表示笛卡尔空间与关节空间关联过程中衍生...

    zhoucheng_Robot
  • MAC:外接其他接盘设置f1——f12功能键位

    MAC 外接接盘f1到f12的功能键不能用,推荐软件:Karabiner 链接在此

    菜菜不吃蔡
  • Linux 学习笔记之超详细基础linux命令 Part 2

    ---------------------------------接Part 1------------------------------

    授客
  • CKafka系列学习文章 - Filebeat对接CKafka(七)

    导语:用CKafka作一个消息缓冲,用Filebeat收集日志,然后将日志传到Ckafka中。

    发哥说消息队列
  • 蒂姆·库克公开信:保护用户数据 FBI我们都敢拒绝

    大数据文摘
  • 无需在数据集上学习和预训练,这种图像修复新方法效果惊人 | 论文

    林鳞 编译自 Github 量子位 出品 | 公众号 QbitAI Reddit上又炸了,原因是一个无需在数据集上学习和预训练就可以超分辨率、修补和去噪的方法:...

    量子位
  • 从linux0.11看一个进程的诞生

    这一篇大致说一下进程的创建,有兴趣的可以参考之前的一些文章或者直接上代码https://github.com/theanarkh/read-linux-0.11...

    theanarkh

扫码关注云+社区

领取腾讯云代金券