所谓的斐波纳契数列是指前2个数是 0 和 1 ,第 i 个数是第 i-1 个数和第i-2 个数的和。大致可以描述为a(n) = a(n-1) + a(n-2) (a >=2)。类似于这样[1, 1, 2, 3, 5, 8, 13 ...]。 具体大家可以百度一下。下面我们来用js获取菲波那契数列的第N个数为多少:
var a = function(n) {
if (n === 1 || n === 2) {
return 1
} else {
return a(n - 1) + a(n - 2)
}
}
console.time('a(44)')
console.log(a(44))
console.timeEnd('a(44)')
以上我们可以比较清晰的看出代码的思路,但是这种方法有一个致命的缺点:效率太差!不信你看:
701408733
VM381:10 a(44): 5768.427734375ms
执行到第44个的时候,已经不能接受了,需要5s多。那我们再来改进一下
var b = (function() {
var cache = {
1: 1,
2: 1
}
return function(n) {
if (cache[n]) {
return cache[n]
} else {
cache[n - 1] = b(n - 1)
cache[n - 2] = b(n - 2)
return cache[n - 1] + cache[n - 2]
}
}
})()
console.time('b(1200)')
console.log(b(1200))
console.timeEnd('b(1200)')
将每一步计算出来的值,保存到了缓存中。效率提升了许多:
2.7269884455406272e+250
VM383:19 b(1200): 0.630126953125ms
var c = function(n) {
var arr = [1, 1]
if (n === 1 || n === 2) {
return 1
}
for (var i = 2; i < n; i ++) {
arr[i] = arr[i - 1] + arr[i - 2]
}
return arr[n - 1]
}
console.time('c(1200)')
console.log(c(1200))
console.timeEnd('c(1200)')
这样效率又进一步提高了不少:
2.7269884455406272e+250
VM436:13 c(1200): 0.36181640625ms
那这样还有没有更快的方法呢?当然有!菲波那契数列是有数学表达式的。我们为何不直接使用数学表达式呢?
var d = function(n) {
return (1/(Math.pow(5, 1/2))) * (Math.pow((1 + Math.pow(5, 1/2))/2, n) - Math.pow((1 - Math.pow(5, 1/2))/2, n))
}
console.time('d(1200)')
console.log(d(1200))
console.timeEnd('d(1200)')
效率如下:
2.7269884455406177e+250
VM428:7 d(1200): 0.424072265625ms
1.第一行表示从ME到空字符所要删除的字符的所以情况 2.第一列表示从空字符到MY所需要插入字符的所有情况 3.斜箭头表示相同字符不需要替换,不相同字符所有替换次数的所有情况
单链表是表示一系列节点的数据结构,其中每个节点指向链表中的下一个节点。 相反,双向链表具有指向其前后元素的节点。与数组不同,链表不提供对链表表中特定索引访问。
最近的一个塔罗牌项目中,有一个洗牌的需求,其实也就是随机打乱数组,遂网上搜了下,再此做个整理…塔罗牌,举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9:
全局唯一标识符(GUID,Globally Unique Identifier)也称作 UUID(Universally Unique IDentifier) 。GUID是一种由算法生成的二进制长度为128位的数字标识符。GUID 的格式为“xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx”
有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。
PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。
链表更加像是数组。链表和数组都是用于存储有序元素的集合,但有几点大不相同,链表的实现不像之前介绍的栈和队列一般依赖于数组(至少我们目前是这样实现的),它必须自己构建类并组织逻辑实现。我们先创建一个Node类
什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a
在开发页面的时候,我们有时候会遇到这种需求:在页面某个dom节点中遍历,找到目标dom节点,我们正常做法是利用选择器document.getElementById(),document.getElementsByName()或者document.getElementsByTagName(),
通过学习本文,你可以掌握以下三点内容:为什么需要时间复杂度;时间复杂度怎么表示;怎样分析一段代码的时间复杂度,相信认真阅读过本文,面对一些常见的算法复杂度分析,一定会游刃有余
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!