[理工] 99電機丙 11 複雜度

看板Grad-ProbAsk作者 (JOU)時間12年前 (2012/02/03 23:45), 編輯推噓3(3推 0噓 15→)
留言18則, 6人參與, 最新討論串1/1
http://i.imgur.com/CLOL6.jpg
這邊直接附上題目與跟同學的討論結果 由於找不到答案 想請問有誰有解答 或是覺得哪邊怪怪的可以來討論下 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.168.98.150
推
02/03 23:49, , 1F
(lgn)^n 應該最大吧??
02/03 23:49, 1F
→
02/04 00:53, , 2F
跟原po一樣
02/04 00:53, 2F
→
02/04 01:49, , 3F
(lgn)^n 我們也想很久 但因為有書說lgn無論幾次都比n小
02/04 01:49, 3F
→
02/04 01:50, , 4F
所以就先暫定當作比n小 不然log法 nloglogn與(lgn)(lgn)
02/04 01:50, 4F
→
02/04 01:50, , 5F
也不是很肯定誰最大
02/04 01:50, 5F
推
02/04 03:51, , 6F
(lg n)^n > 2^n > ... 所以應該是最大的
02/04 03:51, 6F
→
02/04 08:50, , 7F
你們搞錯了吧...你們看書上應該是log(log(log..log(n)))
02/04 08:50, 7F
→
02/04 08:53, , 8F
他會寫成log*n 但是這是ackermann反函數的複雜度
02/04 08:53, 8F
→
02/04 08:55, , 9F
不是(logn)^n 你們可以試想c^n 已經超越polynomial的
02/04 08:55, 9F
→
02/04 08:58, , 10F
函數... 另外 nloglogn絕對大於(logn)^c
02/04 08:58, 10F
→
02/04 08:58, , 11F
上面的c都只是指常數
02/04 08:58, 11F
→
02/04 09:01, , 12F
我錯了....
02/04 09:01, 12F
→
02/04 09:21, , 13F
後來我想了一下你們是不是對 n>(logn)^c for any c
02/04 09:21, 13F
→
02/04 09:22, , 14F
誤解了 如果是常數的話是比n小沒錯 但是如果power是n
02/04 09:22, 14F
→
02/04 09:23, , 15F
的話就會超越 c^n 了喔
02/04 09:23, 15F
→
02/04 11:39, , 16F
所以就(logn)^n最大 其他的就都對了?
02/04 11:39, 16F
推
02/04 14:32, , 17F
log(n)^n用log法來看一定比指數大，其它應該都對
02/04 14:32, 17F
→
09/11 14:52, , 18F
(lgn)^n 我們也 https://daxiv.com
09/11 14:52, 18F
‣ 更多 DiLegend 的文章
文章代碼(AID): #1FB04KlR (Grad-ProbAsk)