對于二進制搜索樹類型的數據結構，我看到Big O標記通常記為O（logn）。如果日志中的字母為小寫“ l”，這是否意味著以自然對數描述的對數e（n）為對數？很抱歉這個簡單的問題，但是我一直很難區分不同的隱式對數。
3 回答
茅侃侃
TA貢獻1842條經驗 獲得超21個贊
一旦用big-O（）表示法，兩者都是正確的。但是，在推導 O（）多項式的過程中，對于二進制搜索，只有log 2是正確的。我認為這種區別是您提出問題的直觀靈感。
另外，以我的觀點，寫O（log 2 N）對于您的示例更好，因為它可以更好地傳達算法運行時間的推導。
在big-O（）表示法中，常數因子被刪除。從一個對數底數轉換為另一對數底數需要乘以一個常數因子。
因此，由于常數因子，O（log N）等于O（log 2 N）。
但是，如果您可以輕松地在答案中輸入log 2 N，則這樣做更具教學意義。在二叉樹搜索的情況下，你是正確的，日志2 N為大O（）運行時的推導過程中引入。
在將結果表示為big-O（）表示法之前，區別非常重要。當推導要通過big-O表示法傳遞的多項式時，在此示例中，在應用O（）表示法之前使用log 2 N 以外的對數是不正確的。一旦使用了多項式通過big-O（）表示法來傳達最壞情況的運行時，使用什么對數就無關緊要了。
- 3 回答
- 0 關注
- 671 瀏覽
添加回答
舉報
0/150
提交
取消