[问题]关于全排列的 hash

C、C++和Java语言
回复
头像
BigSnake.NET
帖子: 12522
注册时间: 2006-07-02 11:16
来自: 廣州
送出感谢: 0
接收感谢: 7 次
联系:

[问题]关于全排列的 hash

#1

帖子 BigSnake.NET » 2007-11-14 13:45

设一个全排列为 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) 的算法 , 有没有更好的?
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。
头像
zhan
帖子: 1880
注册时间: 2005-08-15 0:04
来自: 南7技校
送出感谢: 0
接收感谢: 0
联系:

#2

帖子 zhan » 2007-11-14 14:19

换个思路,你的第一步等价于 在一次排序中移动元素的总次数....


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

看看对不对...
飞得高,飞得低,学习再学习,多少大秘密!
http://zhan.blog.ubuntu.org.cn
zhangsong023
帖子: 768
注册时间: 2006-09-20 19:56
送出感谢: 0
接收感谢: 1 次

#3

帖子 zhangsong023 » 2007-11-14 15:55

觉得ls是对的,第一步的最优算法等同于用一个最优的排序算法后,再由一个0(1)算法得到a[i]的值,而排序算法的最优效率只能达到O(nlogn)
duangenquan
帖子: 2
注册时间: 2007-10-26 13:17
送出感谢: 0
接收感谢: 0

#4

帖子 duangenquan » 2007-11-15 11:46

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

是不是我陷入到树状数组里面去了?
头像
BigSnake.NET
帖子: 12522
注册时间: 2006-07-02 11:16
来自: 廣州
送出感谢: 0
接收感谢: 7 次
联系:

#5

帖子 BigSnake.NET » 2007-11-15 18:24

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

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


第一步是要把整个a算出来,K[i] 是全排列
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。
头像
ttand
帖子: 1743
注册时间: 2005-08-22 14:05
来自: 离开北京
送出感谢: 1 次
接收感谢: 3 次

#6

帖子 ttand » 2007-11-15 19:03

仔细看了你那个是要求算出全部值 还是要排序。。。
上次由 ttand 在 2007-11-15 19:19,总共编辑 2 次。
错过好多好贴,没占到广告位后悔啊
zhangsong023
帖子: 768
注册时间: 2006-09-20 19:56
送出感谢: 0
接收感谢: 1 次

#7

帖子 zhangsong023 » 2007-11-15 19:15

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)
回复

回到 “C/C++/Java”