作者Lizstlin (Lizst)
看板TransCSI
標題[請益] BigO證明觀念以及幾題證明
時間Tue Oct 5 01:05:22 2010
因為老師上課沒講什麼證明範例, 書上也寫得少
自己找題目寫遇到不少瓶頸, 我知道基本觀念是
f(n) = O(n) iff there exist positive constants c and n0 s.t
f(n) <= c*g(n) for all n which n >= n0
那個c 在證明過程中可以隨便假設嗎?
因為總覺得要有一定範圍才可以, 像下面的證明我設1就不知道怎麼繼續下去
證明題如下:
show that n! = O(n^n)
show that n^(2^n) + 6*2(^n) = θ(2^(2^n))
show that n^2 * logn = θ(n^2) is incorrect
大致上就是這些了, 希望有大大不吝指教, 謝謝 (拜)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.202.53
1F：推 Asbarla:C是時間常數 不要為負 10/08 00:59
2F：推 Asbarla:第三個問題用矛盾證法 假設他是對的 就會存在一組C和N0 10/08 01:01
3F：推 Asbarla:帶進去算到最後會發現N會<=(>=)C*xx 很明顯會矛盾 就得證 10/08 01:08
4F：推 Asbarla:bigO 要取C我會取最高項係數加1就是了 同理omega是減1 10/08 01:14