[算法] 求积 [复制链接]

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2008-04-09 10:06 |只看该作者 |倒序浏览

已知：A1 A2 A3 A4 ... An

比如 A[]={2,3,4,5,6,7,8,9};

求出各个Bi（i= 1,2 ...,n)
B1 = A2*A3* ...*An
B2 = A1*A3* ...*An
Bn-1 = A1*...*An-2*An
Bn = A1*A2*...*An-1

要求不能用除法时间复杂度小于等于 o(nlogn)

文库|博客

yecheng_110

小富即安

论坛徽章:: 1

2楼 [报告]

发表于 2008-04-09 10:20 |只看该作者

对空间复杂度没要求？

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

yecheng_110

小富即安

论坛徽章:: 1

3楼 [报告]

发表于 2008-04-09 10:41 |只看该作者

这个图画一下就清楚了

c[1] = 1
c[2] = a[1]
c[3] = c[2] * a[2]
c[n] = c[n - 1] * a[n - 1]

d[1] = 1
d[2] = a[n]
d[3] = d[2] * a[n - 3 + 2];
d[n] = d[n-1] * a[2];

b[1] = c[1] * d[n];
b[2] = c[2] * d[n-1];
b[n] = c[n] * d[1];

[ 本帖最后由 yecheng_110 于 2008-4-9 11:46 编辑 ]

{62F5B39A-CF30-49DF-9D81-567CE62259C2}.JPG (8.24 KB, 下载次数: 35)