24小时热门版块排行榜    

CyRhmU.jpeg
查看: 1144  |  回复: 7

qrr_xmc

新虫 (正式写手)

[求助] 能否证明如下渐进关系已有1人参与

如何证明如下关系:

能否证明如下渐进关系
question.png

M,N为整数。
回复此楼
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wurongjun

专家顾问 (职业作家)

【答案】应助回帖

★ ★ ★ ★ ★
感谢参与,应助指数 +1
qrr_xmc: 金币+5, 有帮助 2015-12-06 08:07:42
分母的第二项j=N时为零!
所以结果不成立!
善恶到头终有报,人间正道是沧桑.
2楼2015-12-04 16:25:45
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

qrr_xmc

新虫 (正式写手)

3楼2015-12-04 16:50:00
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

nagami

木虫 (正式写手)

假设M=N
左式加log,阶乘用Stirling's approximation替代,logN! ~ NlogN-N
累乘变累和后消去了N^2logN,剩下的渐近是O(N^2),个人看法
女靠衣装;男靠金装
4楼2015-12-04 17:51:46
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

nagami

木虫 (正式写手)

引用回帖:
4楼: Originally posted by nagami at 2015-12-04 17:51:46
假设M=N
左式加log,阶乘用Stirling's approximation替代,logN! ~ NlogN-N
累乘变累和后消去了N^2logN,剩下的渐近是O(N^2),个人看法

注意,这个和原问题是没对起来的,log去掉就是指数增长了

» 本帖已获得的红花(最新10朵)

女靠衣装;男靠金装
5楼2015-12-04 17:52:41
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

qrr_xmc

新虫 (正式写手)

送红花一朵
引用回帖:
5楼: Originally posted by nagami at 2015-12-04 17:52:41
注意,这个和原问题是没对起来的,log去掉就是指数增长了...

多谢回复 不是应助回复 无法奖励金币 送朵红花吧

发自小木虫Android客户端
6楼2015-12-06 08:45:42
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hank612

至尊木虫 (著名写手)

★ ★ ★ ★ ★
qrr_xmc(Edstrayer代发): 金币+5, Latex应助 2015-12-08 00:15:08
楼主你好,可以提供一下你的命题的文献出处么? 我推了半天,始终证不出你要的结果,可以麻烦检查一下下面推理是否有错?谢谢

根据nagami 的提示,我对左边式子取对数,再除以N^2,(同时令M/N=a,纯粹为了打字方便),
左边等于

这又等于

由N趋于无穷及定积分的定义,以及, 上式最后化简为



如果a>1, 那么 (a-1)lnN 控制其它所有项,趋于无穷大; 即使a=1, 该式等于3/2,意味着楼主原式大约是. 无论哪种情况,都和O(N^2) 相差十万八千里。

离楼主答案差太多,都不好意思应助了,

» 本帖已获得的红花(最新10朵)

We_must_know. We_will_know.
7楼2015-12-06 23:17:29
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

qrr_xmc

新虫 (正式写手)

送红花一朵
引用回帖:
7楼: Originally posted by hank612 at 2015-12-06 23:17:29
楼主你好,可以提供一下你的命题的文献出处么? 我推了半天,始终证不出你要的结果,可以麻烦检查一下下面推理是否有错?谢谢

根据nagami 的提示,我对左边式子取对数,再除以N^2,(同时令M/N=a,纯粹为了打字方便 ...

多谢回复 等式左边补上log 能成立吗

发自小木虫Android客户端
8楼2015-12-07 16:27:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 qrr_xmc 的主题更新
信息提示
请填处理意见