Re: [其他] big O 大於的證明
※ 引述《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://www.ptt.cc/bbs/Math/M.1663052845.A.DD6.html
推
09/13 15:35,
1年前
, 1F
09/13 15:35, 1F
→
09/13 15:45,
1年前
, 2F
09/13 15:45, 2F
→
09/13 15:45,
1年前
, 3F
09/13 15:45, 3F
討論串 (同標題文章)