| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2736 人关注过本帖, 1 人收藏
标题:杨辉三角的编程,求最佳解答
只看楼主 加入收藏
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
以下是引用中学者在2011-3-1 22:48:47的发言:


不知道呢~~我只是看到那个技术敏感性太差的发言有点激动..没过多考虑.孔明大牛给个浅显易懂的答案.


你想,如果用你这种O(1)的转移方程(f[i,j]=f[i-1,j-1]+f[i-1,j]),那么在转移过程中我们在计算f[i,_]前必定需要保留f[i-1,_]上的所有数据,每当计算出来一个f[i,_]上的记录,对应的我可以删除一个f[i-1,_]上的记录,也就是说我们需要保留的数据是O(n)。这样的分析是在i(1->n) j(1->i)上考虑的,但是我们可以进行不严谨的推广(这样比较好理解),抽象地想,如果要有O(1)的转移,那么计算的过程必定是一滴墨水在纸上扩散的过程,是一条线扫出一个面。

所以,我认为空间复杂度在这样的情况下最小是O(n)。

[ 本帖最后由 卧龙孔明 于 2011-3-1 22:59 编辑 ]

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2011-03-01 22:57
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
这样吧,a[i%2][j] = a[(i-1)%2][j] + a[(i-1)%2][(j-1)];
空间复杂度O(n)

樱花大战,  有爱.
2011-03-01 23:00
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
以下是引用中学者在2011-3-1 23:00:52的发言:

这样吧,a[j] = a[(i-1)%2][j] + a[(i-1)%2][(j-1)];
空间复杂度O(n)


是的,我想单单从复杂度角度看是最理想的情况了。
其实我是想用一些技巧让cpp(C Preprocessor)完成这些任务(仅仅是娱乐),但是因为一些平台相关的问题,我没有去实现。

[ 本帖最后由 卧龙孔明 于 2011-3-1 23:12 编辑 ]

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2011-03-01 23:06
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
一维数组:
a[2*N]
a[(i%2)*N+j] = a[((i-1)%2)*N+j] + a[((i-1)%2)*N+j-1];

樱花大战,  有爱.
2011-03-01 23:38
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:0 
嗯。我也觉得这个复杂度不能再低了。

孔明说的用处理做是什么意思?
是说做好的效果大约是:在预处理阶段就可以把 factorial(n) 替换成对应的数吗?
2011-03-02 15:59
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
《java 核心编程》有一道 杨辉三角的题, java是支持变长数组的,
杨辉三角实际应用的时候,就是用变长数组来节省空间。
这种小儿科, 比什么滚动数组差远了,别激动...

我最近在整理文档、IDE、源文件、资源... ,不跟你们讨论啦

我就是真命天子,顺我者生,逆我者死!
2011-03-02 19:00
huiming
Rank: 2
等 级:论坛游民
帖 子:31
专家分:36
注 册:2010-4-8
收藏
得分:0 
时间复杂度和空间复杂度是对立
a[10][5]二维数组就ok
2011-03-03 10:22
TrexT
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2011-4-23
收藏
得分:0 
回复 8楼 BlueGuy
版主 求教!!!516250887
2011-04-23 15:56
快速回复:杨辉三角的编程,求最佳解答
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026894 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved