作者deathcustom (Full House)
看板Math
标题Re: [其他] big O 大於的证明
时间Tue Sep 13 15:07:23 2022
※ 引述《magic704226 (梅姬?没鸡?傻傻分不清楚)》之铭言：
: O(N^(N/2)) < O(N!)
: 这个要如何证明 ?
给你一个高中生就可以证明的方式
考虑N偶数2n
左式 = (2n)*(2n)*(2n)*....*(2n)
右式 = (2n*1)*((2n-1)*2)*...*(n*(n-1))
左右均为n个元素且右式每一项均大於左式
考虑N为奇数2n+1
左式 = (2n+1)*(2n+1)*...*(2n+1)*sqrt(2n+1)
右式 = (2n+1)*(2n*2)*...*(n*(n+2))*(n+1)
前半部n个连乘没问题(如同偶数)，只需要确认n+1 > sqrt(2n+1)
而且已知对所有自然数成立
QED#
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 218.32.247.8 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1663052845.A.DD6.html
1F：推 Vulpix : 但是big O有order的意思在，还要再多一点东西。 09/13 15:35
2F：→ deathcustom : RHS/LHS > n/2 or sqrt(n/2) 当N趋近inf，n趋近inf 09/13 15:45
3F：→ deathcustom : 因此其上限渐进线(O)的比例趋近inf 09/13 15:45