一起自学前端开发!

前端JS算法入门普及教程

来源:原创    更新时间:2017-08-31 09:12:39    编辑:前端网    浏览:2899

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

首先来认识一下算法的基本概念:


一、基本概念:


1、算法的定义

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


2、判断算法的好坏

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

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

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

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


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


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

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

3、数据结构

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


4、程序与算法的联系与区别

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

(1) 数据结构与算法的联系:

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

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

(2)数据结构与算法的区别:  

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


二、js基本数据结构


1、对象

     

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

(1)在js中创建对象的三种方法:

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

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

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


2、数组

(1)数组的声明方法  :

 arrayObj = new Array(); //创建一个数组。

 

arrayObj = new Array([size]) 创建一个数组并指定长度,注意不是上限,是长度。


arrayObj = new Array([element0[, element1[, ...[, elementN]]]]) 创建一个数组并赋值。


arrayObj = [element0, element1, ..., elementN] 创建一个数组并赋值的简写,注意这里中括号不表示可省略。


(注):注意带“[]”与不带“[]”的区别


(2)数字的常用操作:

数组的元素的访问

数组元素的添加

数组元素的删除

数组的截取和合并

数组的拷贝


数组元素的排序

数组元素的字符串化

(3)数组的运算(传地址) :

 

(4)es5中数组的常用方法(列举常用五种 ,共九种) :

注* 九个方法

Array.prototype.indexOf Array.prototype.lastIndexOf Array.prototype.every Array.prototype.some Array.prototype.forEach Array.prototype.map Array.prototype.filter Array.prototype.reduce Array.prototype.reduceRight


1) indexOf:

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

不使用indexOf时

使用后,

2) filter:

该filter()方法创建一个新的匹配过滤条件的数组。

不用 filter() 时

用了 filter():

3) forEach()

forEach为每个元素执行对应的方法

forEach是用来替换for循环的 。

4) map()

map()对数组的每个元素进行一定操作(映射)后,会返回一个新的数组,

不使用map

使用map之后:

map()是处理服务器返回数据时是一个非常实用的函数 。


5) reduce()

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

说实话刚开始理解这句话有点难度,它太抽象了。

场景: 统计一个数组中有多少个不重复的单词

不使用reduce时:

使用reduce()后 :


2、二维数组与多维数组

二维数组的本质:数组中的元素又是数组。 例如:

二维数组的创建法(以下为未知长度的二维数组)

多维数组创建以及传值:

3、堆和栈

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

栈是限定仅在表头进行插入和删除操作的线性表。

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

在js中模拟效果如下:

 输出效果如下:

 4、列队

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

就好比:现在这个胡同不是死胡同了,队伍可以直接通过。

直接上图:

输出效果如下:

5、链表

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

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

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


链表一般有,单链表、静态链表、循环链表、双向链表

单链表:就是很单一的向下传递,每一个节点只记录下一个节点的信息,就跟无间道中的梁朝伟一样做卧底都是通过中间人上线与下线联系,一旦中间人断了,那么就无法证明自己的身份了,所以片尾有一句话:"我是好人,谁知道呢?”

静态链表:就是用数组描述的链表。也就是数组中每一个下表都是一个“节”包含了数据与指向

循环链表:由于单链表的只会往后方传递,所以到达尾部的时候,要回溯到首部会非常麻烦,所以把尾部节的链与头连接起来形成循环

双向链表:针对单链表的优化,让每一个节都能知道前后是谁,所以除了后指针域还会存在一个前指针域,这样提高了查找的效率,不过带来了一些在设计上的复杂度,总体来说就是空间换时间了

综合下,其实链表就是线性表中针对顺序存储结构的一种优化手段,但是在 语言中由于数组的特殊性(自动更新引用位置),所以我们可以采用对象的方式做链表存储的结构

实现一个最简单的链表关系 :

三、js常用算法


1、递归

      递归算法,是将问题转化为规模缩小的同类问题的子问题,每一个子问题都用一个同样的算法去解决。一般来说,一个递归算法就是函数调用自身去解决它的子问题。

 递归算法的特点:

  1. 在函数过程中调用自身。

  2. 在递归过程中,必须有一个明确的条件判断递归的结束,既递归出口。

  3. 递归算法简洁但效率低,通常不作为推荐算法。

js递归的简单调用



举个递归函数的应用例子,用来调用json的子节点,把所有json中的子节点中包含某个数的 ,都push到一个数组中,然后对其进行绑定。





评论区

表情

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

相关内容

点击排行

随机新闻

评论排行榜