最近在研究算法,书上一直说时间是O（logn）,但是没有明确说logn的底是什么,这样理解是否准确?
问题描述：
最近在研究算法,书上一直说时间是O（logn）,但是没有明确说logn的底是什么,这样理解是否准确?
算法分析中logN没有特殊说明应该是默认2为底,因为以2为底的log函数的相对增长率要大于其他底数情况（如底数为3,4,5……）.作为对时间复杂度的估计,底数为2的O(logN)可以看做是log函数型相对增长率的上界
答
从理论上,无论低是什么都无关紧要,因为不同底的logn之间只存在常数倍的关系,这与n无关,不会影响复杂度的大小.