TA貢獻(xiàn)1842條經(jīng)驗(yàn) 獲得超22個(gè)贊
一旦用big-O（）表示法，兩者都是正確的。但是，在推導(dǎo) O（）多項(xiàng)式的過程中，對于二進(jìn)制搜索，只有l(wèi)og 2是正確的。我認(rèn)為這種區(qū)別是您提出問題的直觀靈感。
另外，以我的觀點(diǎn)，寫O（log 2 N）對于您的示例更好，因?yàn)樗梢愿玫貍鬟_(dá)算法運(yùn)行時(shí)間的推導(dǎo)。
在big-O（）表示法中，常數(shù)因子被刪除。從一個(gè)對數(shù)底數(shù)轉(zhuǎn)換為另一對數(shù)底數(shù)需要乘以一個(gè)常數(shù)因子。
因此，由于常數(shù)因子，O（log N）等于O（log 2 N）。
但是，如果您可以輕松地在答案中輸入log 2 N，則這樣做更具教學(xué)意義。在二叉樹搜索的情況下，你是正確的，日志2 N為大O（）運(yùn)行時(shí)的推導(dǎo)過程中引入。
在將結(jié)果表示為big-O（）表示法之前，區(qū)別非常重要。當(dāng)推導(dǎo)要通過big-O表示法傳遞的多項(xiàng)式時(shí)，在此示例中，在應(yīng)用O（）表示法之前使用log 2 N 以外的對數(shù)是不正確的。一旦使用了多項(xiàng)式通過big-O（）表示法來傳達(dá)最壞情況的運(yùn)行時(shí)，使用什么對數(shù)就無關(guān)緊要了。
TA貢獻(xiàn)1951條經(jīng)驗(yàn) 獲得超3個(gè)贊
Big O表示法不受對數(shù)底數(shù)的影響，因?yàn)椴煌讛?shù)中的所有對數(shù)均與一個(gè)常數(shù)因子相關(guān)，O(ln n)等效于O(log n)。
舉報(bào)