阶乘与幂的一个问题

saintqdd
水牛 2011-01-20 字数 88

n!可以写成质数组合的形式,比如n!=2^x*3^y*5^z....

如何找到一个最小的n,使得n!包含2^100000项

Algorithm 算法
17 个回复
cjycleaner
一只快死的鸟|乾坤一掷 2011-01-20

n内有多少个2的因数,卡个界就行了

【 在 saintqdd (水牛) 的大作中提到: 】

: n!可以写成质数组合的形式,比如n!=2^x*3^y*5^z....

: 如何找到一个最小的n,使得n!包含2^100000项

saintqdd
水牛 2011-01-20

如果2^x项,x非常大呢。比如10000000000

【 在 cjycleaner (一只快死的鸟|乾坤一掷) 的大作中提到: 】

: n内有多少个2的因数,卡个界就行了

Locke
没想好 2011-01-20

你要做渐进性质分析?

【 在 saintqdd (水牛) 的大作中提到: 】

: 如果2^x项,x非常大呢。比如10000000000

saintqdd
水牛 2011-01-20

不是,就是对于一个超大的x,如何快速的找到最小的n,使其n!包含2^x项。找到一个确定的值。而且速度比较快。x可以在10位到15位之间的大数

【 在 Locke (没想好) 的大作中提到: 】

: 你要做渐进性质分析?

xreborner
xreborner 2011-01-20

非常简单

对于给定的n,计算相应的x是O(lg n)时间复杂度

于是可用二分法求给定x对应的n,总时间复杂度最多为O(lg^2 n)

【 在 saintqdd (水牛) 的大作中提到: 】

: 不是,就是对于一个超大的x,如何快速的找到最小的n,使其n!包含2^x项。找到一个确定的值。而且速度比较快。x可以在10位到15位之间的大数

saintqdd
水牛 2011-01-20

给定的n,计算x是lg n? 算不出吧。这个x对应的是n!(n的阶乘)

【 在 xreborner (xreborner) 的大作中提到: 】

: 非常简单

: 对于给定的n,计算相应的x是O(lg n)时间复杂度

: 于是可用二分法求给定x对应的n,总时间复杂度最多为O(lg^2 n)

wywcgs
乌鸦 2011-01-20

判一下含多少2, 多少4, 多少8, ......., 多少2^k, 然后求和

这不是 O(lgn) ?

【 在 saintqdd (水牛) 的大作中提到: 】

: 给定的n,计算x是lg n? 算不出吧。这个x对应的是n!(n的阶乘)

saintqdd
水牛 2011-01-20

多谢指点,明白喽

【 在 wywcgs (乌鸦) 的大作中提到: 】

: 判一下含多少2, 多少4, 多少8, ......., 多少2^k, 然后求和

: 这不是 O(lgn) ?

cjycleaner
一只快死的鸟|乾坤一掷 2011-01-20

实际上n就是比x略大的一个数

【 在 xreborner (xreborner) 的大作中提到: 】

: 非常简单

: 对于给定的n,计算相应的x是O(lg n)时间复杂度

: 于是可用二分法求给定x对应的n,总时间复杂度最多为O(lg^2 n)

: ...................

skycracker
walker 2011-01-21

。。。。。

这个问题讨论复杂度 没有这么个trivial,

复杂度是相对于input length来说的。

一个数n, 如果用二进制来表示, 需要的长度是log n bits,

如果一个数可以被2^k整除 那么二进制中他的结尾有k 0' bits.

所以每判断一个数需要的时间是O(k) 或者O(log n), 而不是你说的 O(1).

(当一个数足够长的时候 远远超过32/64位)

但是同时这个问题又没有那么复杂。

从1到n这些数字中

结尾一个0的有n/2,

结尾两个0的有n/4

....

结尾k个0的有n/2^k.

假如这些数中结尾最多有k个0,

那么0的总数就是。。。, 不难推导一个表达式出来

用这个表达式 O(1)就能算出来 结果

或者严格的说 需要O(log n), 考虑到数字的长度

【 在 wywcgs (乌鸦) 的大作中提到: 】

: 判一下含多少2, 多少4, 多少8, ......., 多少2^k, 然后求和

: 这不是 O(lgn) ?

wywcgs
乌鸦 2011-01-21

乱七八糟, 完全不知道你在说些什么

你说得跟我说的有啥区别?

------------------------

好吧, 我看明白你在说啥了, 咱俩说的根本不是一个东西.

另外, 您挺厉害, 除法取整再求和也能搞出O(1)的公式直接算. 拜求公式, 鄙人绞尽脑

汁也只能想到O(lgn lglgn)的算法.

【 在 skycracker (walker) 的大作中提到: 】

: 。。。。。

: 这个问题讨论复杂度 没有这么个trivial,

: 复杂度是相对于input length来说的。

: ...................

skycracker
walker 2011-01-21

那只能说明你想的还是不够

check

Hardy & Wright, Th. 416

An Introduction to the Theory of Numbers

【 在 wywcgs (乌鸦) 的大作中提到: 】

: 乱七八糟, 完全不知道你在说些什么

: 你说得跟我说的有啥区别?

: ------------------------

: ...................

wywcgs
乌鸦 2011-01-21

扫了下目录, 从头到尾没发现相关章节. 看了几章的内容也没有类似的

说细点, 在哪一章?

【 在 skycracker (walker) 的大作中提到: 】

: 那只能说明你想的还是不够

: check

: Hardy & Wright, Th. 416

: ...................

CTO
天不生仲尼,万古如长夜 2011-01-21

[n/2]+[n/4]+[n/8]+[n/16]+....=100000

时间复杂度:log_2(100000)

【 在 saintqdd (水牛) 的大作中提到: 】

: 标  题: 阶乘与幂的一个问题

: 发信站: 水木社区 (Thu Jan 20 16:38:58 2011), 站内

: n!可以写成质数组合的形式,比如n!=2^x*3^y*5^z....

: 如何找到一个最小的n,使得n!包含2^100000项

: --

wxstorm
企鹅 2011-01-21

你那个O(1)时间就能算出结果不对的。

n/2+ n/4 +.....这个求和怎么在O(1)算出来,要lgn的

ls说的lgn是这个求和的lgn

不是数字的Bits导致的lgn,如果把这个加进去,就是lgn * lgn了

而且复杂度一般不分析这个bits的,分析的话那很多算法都是伪多项式算法了。

都是O(...)* O(2^p)。都是关于Bits的指数级算法

【 在 skycracker (walker) 的大作中提到: 】

: 。。。。。

: 这个问题讨论复杂度 没有这么个trivial,

: 复杂度是相对于input length来说的。

: ...................

wywcgs
乌鸦 2011-01-21

严格来说复杂度分析是要分析这个bits的....

数论相关算法, 复杂度基本都要按照这个bits为单位来算。只是很多领域的问题, 这个

不是主要影响复杂度的因素而已. 比如说图论主要因素是V和E, 像什么普通的四则运算

就完全认为是O(1)完成的了....

另外,分析bits也不一定就是伪多项式。那个人说得还是很对的,是相对于输入规模来

说话。输入一个数n,那么输入规模就是lgn。如果输入n个数,那么输入规模就是n和

lgm。如果仅仅是给一个数n要你求n!里面2^x的x,那么确实是要以lgn为单位计算。

【 在 wxstorm (企鹅) 的大作中提到: 】

: 你那个O(1)时间就能算出结果不对的。

: n/2+ n/4 +.....这个求和怎么在O(1)算出来,要lgn的

: ls说的lgn是这个求和的lgn

: ...................

wxstorm
企鹅 2011-01-21

是啊,bits现在大多数最多不就64么,bits都64了,那个量级的n。。。几个算法能跑出来。。

【 在 wywcgs (乌鸦) 的大作中提到: 】

: 严格来说复杂度分析是要分析这个bits的....

: 数论相关算法, 复杂度基本都要按照这个bits为单位来算

: 只是很多领域的问题, 这个不是主要影响复杂度的因素而已. 比如说图论主要因素是V和E,

: ...................