[理工]資結 big-oh問題

作者: SIGNAL2017 (信號2017)   2018-04-05 04:40:57
https://i.imgur.com/euzk04F.jpg?1
如圖主要想請問在第四點中用鉛筆框起來的地方[就是hint地方],想知道為何
(log n)^2=O(n),因為無法照到題目所以想說直接用打的好了,這題主要題目是在問
說判斷(loglog n)!是否為Polynomial-bounded,前面取log之後變成那樣都懂,
但是不知道為何(log n)^2=O(n),因為我想說(log n)^2是對數等級,為何會等於
多項式等級。這邊是洪逸上課的筆記,不知道是哪裡想錯了,還是我有抄錯地方@@?
作者: ray4452 (ray)   2018-04-05 08:46:00
並不是說等於,O(n)是成長率不超過n,所以說"對數"等級不超過"多項式"也可以是O(n)
作者: plsmaop (plsmaop)   2018-04-05 11:01:00
那個等於當成屬於看待
作者: SIGNAL2017 (信號2017)   2018-04-05 13:32:00
啊......對,我懂了 感恩

Links booklink

Contact Us: admin [ a t ] ucptt.com