作者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/m.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