作为前端开发者而言,可能不会像后端开发那样遇到很多的算法和数据结构问题,但是不论是做前端、 服务端还是客户端, 任何一个程序员都会开始面对更加复杂的问题, 这个时候算法和数据结构知识就变得不可或缺,它是编程能力中很重要的一部分。

算法是一组完成任务的指令,任何代码片段都可以视为算法。通俗的讲我们大概可以理解其为数据结构和逻辑结构结合后的合理工作机制。算法让我们的程序更加流畅和高效的进行工作。

算法的时间复杂度和空间复杂度合称为算法的复杂度,以此判断算法的好或者坏。

首先,这个算法必须是正确的 其次,好的算法应该是友好的,便于人们理解和交流,并且是机器可执行的。 这个算法还需要足够健壮,即当输入的数据非法或不合理时,也能适当的做出正确的反应或进行相应的处理 最后它还必须拥有高效率和低存储量要求。 时间复杂度和空间复杂度 占的地方越小,算得越快的算法才是好算法。

(1) 时间复杂度大体估计程序运行的速度 ,通过时间复杂度的算法得到算法质量,速度越快当然越好。

(2)、一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。

固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。

可变空间,这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模,S(n)表示空间复杂度。

数据结构,顾名思义,就是数据之间的结构关系,或者理解成数据元素相互之间存在的一种或多种特定关系的集合。 它是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科 。

算法+数据结构=应用程序。算法是程序设计的核心,算法的好坏很大程度上决定了一个程序的效率。一个好的算法可以降低程序运行的时间复杂度和空间复杂度。先选出一个好的算法,再配合以一种适宜的数据结构,这样程序的效率会大大提高。

程序=算法+数据结构。数据结构是算法实现的基础,算法总是要依赖于某种数据结构来实现的。往往是在发展一种算法的时候,构建了适合于这种算法的数据结构。 算法的操作对象是数据结构。算法的设计和选择要同时结合数据结构,简单地说数据结构的设计就是选择存储方式,如确定问题中的信息是用数组存储还是用普通的变量存储或其他更加复杂的数据结构。算法设计的实质就是对实际问题要处理的数据选择一种恰当的存储结构,并在选定的存储结构上设计一个好的算法。不同的数据结构的设计将导致差异很大的算法。数据结构是算法设计的基础。

(用一个形象的比喻来解释:开采煤矿过程中,煤矿以各种形式深埋于地下。矿体的结构就像相当于计算机领域的数据结构,而煤就相当于一个个数据元素。开采煤矿然后运输、加工这些“操作”技术就相当于算法。)显然,如何开采,如何运输必须考虑到煤矿的存储(物理)结构,只拥有开采技术而没有煤矿是没有任何意义的。算法设计必须考虑到数据结构,算法设计是不可能独立于数据结构的。 另外,数据结构的设计和选择需要为算法服务。如果某种数据结构不利于算法实现它将没有太大的实际意义。知道某种数据结构的典型操作才能设计出好的算法。 总之,算法的设计同时伴有数据结构的设计,两者都是为最终解决问题服务的。

数据结构关注的是数据的逻辑结构、存储结构以及基本操作,而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想,数据结构则是这些思想的逻辑基础。

在前面有讲到面向对象编程思想, 是一种基于对象( – d)的语言,你遇到的所有东西几乎都是对象(万物皆对象)。 而想要在js中创建一个对象的方法则有三种:

使用内置对象 :就是使用js原生的内置对象,通过 语言原生对象的构造方法,实例化出一个新的对象。如下:

使用JSON符号 : JSON是 原生格式,这意味着在 中处理JSON数据不需要任何特殊的API或者工具包, 默认将JSON当做一个对象处理。 将对象传递给一个变量,例如:

自定义对象构造 : 创建高级对象构造有两种方式:使用“this”关键字构造、使用原型prototype构造。如:

indexOf()方法返回在该数组中第一个找到的元素位置,如果它不存在则返回-1。

reduce()可以实现一个累加器的功能,将数组的每个值(从左到右)将其降低到一个值。

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

就好比:一个死胡同,前面是“此路不通”,只有一个入口,如果一队人进入,只能队尾变对首出去。

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

我们可以看到在 概念中的队列与栈都是一种特殊的线性表的结构,也是一种比较简单的基于数组的顺序存储结构。由于 的解释器针对数组都做了直接的优化,不会存在在很多编程语言中数组固定长度的问题(当数组填满后再添加就比较困难了,包括添加删除,都是需要把数组中所有的元素全部都变换位置的, 的的数组确实直接给优化好了,如push,pop,shift,unshift,split方法等等…)

线性表的顺序存储结构,最大的缺点就是改变其中一个元素的排列时都会引起整个合集的变化,其原因就是在内存中的存储本来就是连贯没有间隙的,删除一个自然就要补上。针对这种结构的优化之后就出现了链式存储结构,换个思路,我们完全不关心数据的排列,我们只需要在每一个元素的内部把下一个的数据的位置给记录就可以了,所以用链接方式存储的线性表简称为链表,在链式结构中,数据=(信息+地址)

链式结构中,我们把地址也可以称为“链”,一个数据单元就是一个节点,那么可以说链表就是一组节点组成的合集。每一个节点都有一个数据块引用指向它的下一个节点

单链表:就是很单一的向下传递,每一个节点只记录下一个节点的信。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注