精易论坛

标题: 浅谈算法重要性优化资源网关于斐波那契数列算法的源码 [打印本页]

作者: Sao熊 时间: 2021-6-10 17:17
标题: 浅谈算法重要性优化资源网关于斐波那契数列算法的源码
无意间发现易语言资源网上层有开源了一个关于斐波那契数列数列的算法。
易语言资源网原来递归法地址：易语言斐波那契数列演示源码 - 易语言资源网 (eyuyan.la)

无聊打发时间下载看了一下，发现该开源是采用原始的递归方法，为了让更多易友了解到算法重要性，所以优化了一下这里补充提交上来。

首先什么是斐波那契数列？
0,1,1,2,3,5,8,13,21,34,55……
该数列规律：
设下标为x,则f(x)=f(x-2)+f(x-1)
通俗讲就是某一位置的数，为前两数的和
其实这本是算法常考问题。原易语言资源网中采用最原始的递归方案，该方案由于时间复杂度太高，且递归方案不适合较大值，我测试了之前源码x超过30将会巨慢甚至直接卡死。
优化代码采用矩阵运算速度更快，即便x很大也基本没有什么问题。

源码基于原易语言资源网源码上直接新增两个按钮作为演示对比。

发这个源码的目的就是为了让更多的易友认识到算法优化的重要性。

补充内容 (2021-6-14 03:35):
试了下水被发现了，补充真正的O(lgn)时间复杂度算法
链接：https://pan.baidu.com/s/1GtzQraoLfXNhpE1taAtBDw
提取码：rjx6

作者: 53770zhang 时间: 2021-6-10 17:26
这个要学习一下

作者: Sao熊 时间: 2021-6-10 17:29

53770zhang 发表于 2021-6-10 17:26
这个要学习一下

有点干，估计看的人不多。纯无聊。。。

作者: 喵帕斯和艾希 时间: 2021-6-10 17:32

作者: 1185384801 时间: 2021-6-10 17:58
斐波那契数列是有通项公式的吧

作者: Sao熊 时间: 2021-6-10 18:12

1185384801 发表于 2021-6-10 17:58
斐波那契数列是有通项公式的吧

是的，用易实现通项公式矩阵运算降低算法的时间复杂度。那么问题来了，编程实现斐波那契数列三种方案的时间复杂度分别是多少？{:3_48:}

作者: 1185384801 时间: 2021-6-10 18:15

-信念。发表于 2021-6-10 18:12
是的，用易实现通项公式矩阵运算降低算法的时间复杂度。那么问题来了，编程实现斐波那契数列三种方案的时 ...

通项应该是O(1)
递归应该是O(n)
但并不完全取决于O()，因为指数运算速度谁也说不准

作者: 汉族 时间: 2021-6-10 18:19
算法历来都是真理

作者: Sao熊 时间: 2021-6-10 18:21

1185384801 发表于 2021-6-10 18:15
通项应该是O(1)
递归应该是O(n)
但并不完全取决于O()，因为指数运算速度谁也说不准 ...

这个是矩阵运算复杂度为O (log n) 跟通项式还不一样，不过速度上是绝对的要优化与原来的递归，下载了测试一下你就知道了。

作者: faith0 时间: 2021-6-10 18:25

这个要学习一下

作者: 难解 时间: 2021-6-10 18:26
看看看看

作者: Sao熊 时间: 2021-6-10 18:41

汉族发表于 2021-6-10 18:19
算法历来都是真理

基础算法入门题，主要是这个比较明显能看出区别，外加之前好像没有用易实现的demo，所有发上来，让没接触过的小伙伴认识到算法的重要性。顺带回答甲方常发生的一个问题，同样的实现为什么价格有高有低。

作者: 137240129 时间: 2021-6-10 18:55
下载下来看看

作者: 1123 时间: 2021-6-10 20:10
66666666666666

作者: 谈谈的味道 时间: 2021-6-10 20:10
这是你们大神研究的东西...

作者: 就是那个秋 时间: 2021-6-10 20:16
好家伙斐波那契

作者: weirdo_ 时间: 2021-6-10 20:22
这是你们大神研究的东西...

作者: Sao熊 时间: 2021-6-10 20:49

liwanqiu 发表于 2021-6-10 20:16
好家伙斐波那契

好家伙 liwanqiu

作者: dych1688 时间: 2021-6-10 20:58
这是你们大神研究的东西...

作者: 网络注册络员 时间: 2021-6-10 21:04
不错不错的

作者: oycs429 时间: 2021-6-10 21:52
让江小白来看看帖子里藏了啥好东西~~~

作者: Sao熊 时间: 2021-6-10 22:08

oycs429 发表于 2021-6-10 21:52
让江小白来看看帖子里藏了啥好东西~~~

江小白是谁

作者: huhu 时间: 2021-6-10 22:39
来学习一下高级技法，感谢分享！！！！！！！！

作者: wxb130260 时间: 2021-6-11 08:17
谢谢楼主分析

作者: xo37 时间: 2021-6-11 08:36
来，来来来，学习下算法

作者: hrb011011 时间: 2021-6-11 08:52
学习！

作者: wjswzj0 时间: 2021-6-11 09:09
感谢分享，很给力！~

作者: 风中冰雨 时间: 2021-6-11 09:13
看看。。。。。

作者: jiang910615 时间: 2021-6-11 10:05
学习学习

作者: 广二爷xxoo 时间: 2021-6-11 10:07
我喜欢你斐波那契数

作者: 编长墨迹 时间: 2021-6-11 10:36
算法！楼主已经脱离低级趣味了！

作者: A9952 时间: 2021-6-11 10:37
这个我觉的挺好的啊

作者: Aa798040941 时间: 2021-6-11 12:59
不错不错

作者: 晨晨666 时间: 2021-6-11 13:25
学习一下

作者: Sao熊 时间: 2021-6-11 16:55

风中冰雨发表于 2021-6-11 09:13
看看。。。。。

评精团是集体翘班了嘛

作者: lzgking 时间: 2021-6-11 17:39
谢谢分享学习一下~~~~

作者: 古巷孤猫 时间: 2021-6-11 18:23
66666666666666666666

作者: bianyuan456 时间: 2021-6-11 19:17
感谢分那些

作者: 深圳梦 时间: 2021-6-11 22:27
感谢分享，很给力！~

作者: zzzyf 时间: 2021-6-12 02:13
#在这里快速回复# 感谢分享，很给力！~

作者: 丿夜曲 时间: 2021-6-12 09:38
纠正一下，易语言资源网里那个递归版本的时间复杂度为O(2^n)

作者: 斜飞 时间: 2021-6-12 15:20
过来查看下

作者: ujff77 时间: 2021-6-12 16:35
有意思哦

作者: 神女软件定制 时间: 2021-6-13 12:54
kankan.......

作者: Sao熊 时间: 2021-6-13 13:51

神一样的女人发表于 2021-6-13 12:54
kankan.......

女人？呵呵

作者: 神女软件定制 时间: 2021-6-13 15:05

丿夜曲发表于 2021-6-12 09:38
纠正一下，易语言资源网里那个递归版本的时间复杂度为O(2^n)

你优化的这个，复杂度不是O(n)吗

作者: 司徒西 时间: 2021-6-13 19:12
感谢分享，很给力！~

作者: 酷易自绘 时间: 2021-6-13 20:40
感谢分享，很给力！

作者: Sao熊 时间: 2021-6-14 03:36

神一样的女人发表于 2021-6-13 15:05
你优化的这个，复杂度不是O(n)吗

O（lgn）的补充上传了，

被发现了，果然不是女人

作者: z899505cqz 时间: 2021-6-14 07:14
嘿嘿,有意思11111

作者: z899505cqz 时间: 2021-6-14 08:47

.版本 2
.子程序 fff, 整数型
.参数 n, 整数型
.局部变量 a, 整数型
.局部变量 b, 整数型
.局部变量 c, 整数型
.如果真 (n ＜ 2)
返回 (n)
.如果真结束
a ＝ 0
b ＝ 1
.计次循环首 (n － 1, )
c ＝ a ＋ b
a ＝ b
b ＝ c
.计次循环尾 ()
返回 (c)
.子程序 ffff, 整数型
.参数 n, 整数型
.局部变量 a, 整数型, , "0"
.局部变量 i, 整数型
重定义数组 (a, 假, n)
.如果真 (n ＜ 2)
返回 (0)
.如果真结束
a [1] ＝ 0
a [2] ＝ 1
.计次循环首 (n － 2, i)
a [i ＋ 2] ＝ a [i ＋ 1] ＋ a [i]
.计次循环尾 ()
返回 (a [n])
这种直观的写法不对么?为何要矩阵运算

复制代码

作者: Sao熊 时间: 2021-6-14 13:41

z899505cqz 发表于 2021-6-14 08:47

因为你这是O(n)，补充上传为O(lgn)

作者: 吠云 时间: 2021-6-14 22:50

谢谢楼主分享

作者: 韦贝贝 时间: 2021-6-15 10:55
算法之美

作者: ybyxzyyx 时间: 2021-6-15 17:25
算法之美

作者: sinewtec 时间: 2021-6-16 14:30
感谢分享，很给力！~

作者: 老鱼科技 时间: 2021-6-16 17:09
算法之美

作者: 雾松 时间: 2021-6-17 09:41

算法之美

作者: 一尘天下 时间: 2021-6-20 12:24

算法之美

作者: Dream琳 时间: 2021-8-3 16:30
支持老哥！！！！！！！！！！！

欢迎光临精易论坛 (https://125.confly.eu.org/)