JavaScript时间复杂度和空间复杂度实例分析
导读:本文共1889字符,通常情况下阅读需要6分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 前言时间复杂度和空间复杂度是衡量一个算法是否优秀的标准,通常我们比较两个算法时会用到以下两种方法:预先估算:就是说在算法设计出来之后,根据算法中的步骤,去估算这个算法所需的时间复杂度和空间复杂度,然后两个进行比较,选择更优秀的那个;事后统计:根据两个算法分别编写一个可执行程序/脚本,交给计算机去执行,分别记录两个算法所需要的时间复杂度和空间复杂度,然后两个进行比... ...
目录
(为您整理了一些要点),点击可以直达。时间复杂度和空间复杂度是衡量一个算法是否优秀的标准,通常我们比较两个算法时会用到以下两种方法:
预先估算:就是说在算法设计出来之后,根据算法中的步骤,去估算这个算法所需的时间复杂度和空间复杂度,然后两个进行比较,选择更优秀的那个;
事后统计:根据两个算法分别编写一个可执行程序/脚本,交给计算机去执行,分别记录两个算法所需要的时间复杂度和空间复杂度,然后两个进行比较,选择更优秀的那个。、
通常情况下我们都会采用第一种方式进行对比,因为第二种在不同环境、不同语言、不同计算机下的运行结果是有差异的,而且第二种的工作量也要比第一种要大。
所谓的时间复杂度就是用于定性描述算法所运行需要花费的时间,所谓的定性就是大概进行描述一下运行时间的趋势,不会去具体到运行需要多少秒;时间复杂度通常用大O
来表示,例如O(1)
、O(n)
、O(logn)
等。
接下来我们通过具体的代码来展示一下时间复杂度,这样更方便去理解:
O(1)
因为在这个代码中,这两行代码永远只执行一次,所以时间复杂度是`O(1)`
O(n)
在上面的代码中,运行时间取决与`n`,所以时间复杂度是`O(n)`。
O(logn)
如果是下面这种情况:
它的时间复杂度是O(1) + O(n)
,它最终的时间复杂度是O(n)
,两个时间复杂度相加的话一般会忽略较小的那个。
如果是两个时间复杂度相乘的话,例如下面这段代码:
这段代码的时间复杂度是O(n^2)
,如果是相乘的话会将两个时间复杂度进行相乘。
空间复杂度与时间复杂度差不多,表示的是算法在运行过程中临时占用存储空间的大小的一个计量单位,
现在我们来看一下几个例子:
O(1)
因为在这个代码中,仅仅定义了一个临时变量,所以空间复杂度是`O(1)`
O(n)
在上面的代码中,我们声明了一个数组,每循环一次都要往数组中存储一个变量,所以时间复杂度是`O(n)`
O(n^2)
JavaScript时间复杂度和空间复杂度实例分析的详细内容,希望对您有所帮助,信息来源于网络。