頁:
[1]
問個數學問題
log(n^2) log(n)^2(logn)^2
log^2n
有何不同?
Big-o等級又有什麼不同?
謝謝
<div></div> log(n*n)
log(n)*log(n)
結果不一樣 log(n)^2
(logn)^2
log^2n
這三個一樣呀 看你怎寫而已
log(n^2)跟上面三個不一樣
舉例
log(10)*log(10)=1*1=1
log(10*10)=2
不一樣
從big-O 角度來看
log(n)^2 會比 log(n^2) 發散的快 本帖最後由 boxwayne444 於 2017-4-30 08:14 PM 編輯
因為很多人說log(n^2)=log(n)^2
但是實際上我把它用計算機計算 log(n)^2 卻等於(logn)^2
但是鑒於前幾年前有新聞說計算機有式子算錯
所以怕怕的 上來確認一下
所以說log(n)^2≧log(n^2)
也就是說log(n)^2=Ω(log(n^2))⇔log(n^2)=O(log(n)^2)?
如果是這樣我應該知道了
還有錯請指正 謝謝{:36:}
另外
log(n)^2
log(n^2)
兩者應該不是屬於同一個等級吧?
log(n)^2是log(n)^2等級log(n^2)是logn等級?
...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 我們從基礎面來看會比要較清楚,在數學上log代表以10為底
log(a * b) = log(a) + log(b),所以log(n^2) = log(n * n) = 2 * log(n)
再來是log(n^2)是否和log(n)^2相等,我們n代10就知道
log(n^2) = log(100) = 2,log(n)^2 = log(10)^2 = 1,不相等
n改代100,log(n^2) = log(10000) = 4,log(n)^2 = log(100)^2 = 4,相等
以此類推,n代100以上,log(n)^2≧log(n^2)才會成立
Big-o是用來計算程式上時間複雜度的度量衡O(X),n則用來代表要計算的量
若X為常數,則不管計算量多寡,程式執行時間都一樣,例如計算1+n = ?
若X = n,則程式執行時間會和n的大小成正比,例如計算1+到n的總數
若X = log(n),則程式執行時間會和log(n)成正比,例如quick sort是n*log(n)
以此類推
因此log(n^2)因為和n成正比,屬於log(n)等級...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><br><br><br><br><br><div></div> log(n^2) = 2logn
(logn)^2 = logn * logn
O(log(n^2)) = O(log(n))
O((log n)^2) > O(log(n))
頁:
[1]