当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 7 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : [问题]关于全排列的 hash
帖子发表于 : 2007-11-14 13:45 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
设一个全排列为 K[i], 1<=i<=n
(1) 令a[i] = { K[1..i] 中小于等于 K[i+1] 的元素的个数, 1<=i<=(n-1) },
(2) 然后由a[i]可以在O(n)内算出 Z = sum( a[i]*i! ), 1<=i<=(n-1)

第一步我只想到 O(nlogn) 的算法 , 有没有更好的?


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
2 楼 
 文章标题 :
帖子发表于 : 2007-11-14 14:19 
头像

注册: 2005-08-15 0:04
帖子: 1880
地址: 南7技校
送出感谢: 0 次
接收感谢: 0 次
换个思路,你的第一步等价于 在一次排序中移动元素的总次数....


排序算法最好也就 O(nlogn) 了....

看看对不对...


_________________
飞得高,飞得低,学习再学习,多少大秘密!
http://zhan.blog.ubuntu.org.cn


页首
 用户资料  
 
3 楼 
 文章标题 :
帖子发表于 : 2007-11-14 15:55 

注册: 2006-09-20 19:56
帖子: 768
送出感谢: 0 次
接收感谢: 1
觉得ls是对的,第一步的最优算法等同于用一个最优的排序算法后,再由一个0(1)算法得到a[i]的值,而排序算法的最优效率只能达到O(nlogn)


页首
 用户资料  
 
4 楼 
 文章标题 :
帖子发表于 : 2007-11-15 11:46 

注册: 2007-10-26 13:17
帖子: 2
送出感谢: 0 次
接收感谢: 0 次
题目有些地方不是很明确:
1)如果是全排列,也就是K[i]的取值在1...n中,那么很明显,可以用树状数组,复杂度是o(n)可以搞定
2)如果K[i]取值是不确定的,用排序之类的算法最好的复杂度也就是o(nlogn
不知道大家是怎么用排序算法 的
我是这样想的:
对每一个数字有它的编号,然后排序,再利用树状数组做。
复杂度是o(nlogn) + o(n) --> o(nlogn)

是不是我陷入到树状数组里面去了?


页首
 用户资料  
 
5 楼 
 文章标题 :
帖子发表于 : 2007-11-15 18:24 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
duangenquan 写道:
题目有些地方不是很明确:
1)如果是全排列,也就是K[i]的取值在1...n中,那么很明显,可以用树状数组,复杂度是o(n)可以搞定
2)如果K[i]取值是不确定的,用排序之类的算法最好的复杂度也就是o(nlogn
不知道大家是怎么用排序算法 的
我是这样想的:
对每一个数字有它的编号,然后排序,再利用树状数组做。
复杂度是o(nlogn) + o(n) --> o(nlogn)

是不是我陷入到树状数组里面去了?


第一步是要把整个a算出来,K[i] 是全排列


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
6 楼 
 文章标题 :
帖子发表于 : 2007-11-15 19:03 
头像

注册: 2005-08-22 14:05
帖子: 1743
地址: 离开北京
送出感谢: 1
接收感谢: 3
仔细看了你那个是要求算出全部值 还是要排序。。。


_________________
错过好多好贴,没占到广告位后悔啊


最后由 ttand 编辑于 2007-11-15 19:19,总共编辑了 2 次

页首
 用户资料  
 
7 楼 
 文章标题 :
帖子发表于 : 2007-11-15 19:15 

注册: 2006-09-20 19:56
帖子: 768
送出感谢: 0 次
接收感谢: 1
BigSnake.NET 写道:
duangenquan 写道:
题目有些地方不是很明确:
1)如果是全排列,也就是K[i]的取值在1...n中,那么很明显,可以用树状数组,复杂度是o(n)可以搞定
2)如果K[i]取值是不确定的,用排序之类的算法最好的复杂度也就是o(nlogn
不知道大家是怎么用排序算法 的
我是这样想的:
对每一个数字有它的编号,然后排序,再利用树状数组做。
复杂度是o(nlogn) + o(n) --> o(nlogn)

是不是我陷入到树状数组里面去了?


第一步是要把整个a算出来,K[i] 是全排列


那就应该是了,o(nlogn)+n*o(1)-->o(nlogn)


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 7 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:Yahoo [Bot] 和 3 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译