严蔚敏老师的《数据结构》里，关于时间复杂度的写法，譬如logn，这个对数函数的底数是多少啊

严蔚敏老师的《数据结构》里，关于时间复杂度的写法，譬如logn，这个对数函数的底数是多少啊

算法中log级别的时间复杂度都是由于使用了分治思想,这个底数直接由分治的复杂度决定。如果采用二分法,那么就会以2为底数,三分法就会以3为底数,其他亦然。不过无论底数是什么,log级别的渐进意义是一样的。也就是说该算法的时间复杂度的增长与处理数据多少的增长的关系是一样的。



扩展资料：
时间复杂度的计算方法
（1）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。
记作T(n)=O(f(n))，称O(f(n))
为算法的渐进时间复杂度，简称时间复杂度。
（2）在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级。
（3）在pascal中比较容易理解，容易计算的方法是：看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。

参考资料来源：百度百科-时间复杂度

还用问吗，计算机都是二进制……你说底数是几……

一般都是2为底数

如果没有特别说明，像logn这样的，一般底数是10，这个是毋庸置疑的。但我所了解的严蔚敏老师的《数据结构》里，一般对数都是有底数的，像这种求复杂度的一般底数是2的比较多，像这样logn的一般是不会在《数据结构》中出现，在数学方面会出现的比较多，是以10为底的。如果出现的话，觉得还是以10为底的（除书中特别声明）。

算法中log级别的时间复杂度都是由于使用了分治思想，这个底数直接由分治的复杂度决定。如果采用二分法，那么就会以2为底数，三分法就会以3为底数，其他亦然。 不过无论底数是什么，log级别的渐进意义是一样的。也就是说该算法的时间复杂度的增长与处理数据多少的增长的关系是一样的。 假设有底数为2和3的两个对数函数，如下图。 当X取N（数据规模）时，求所对应的时间复杂度得比值，即对数函数对应的y值，用来衡量对数底数对时间复杂度的影响。 比值为log2 N / log3 N，运用换底公式后得：(lnN/ln2) / (lnN/ln3) = ln3 / ln2，ln为自然对数，显然这是个常数，与变量N无关。 因此，不写底数并没有影响。 扩展资料： 时间复杂度的分析优势。 可以肯定的说，运行程序，把代码跑一遍，根据统计监控，能够获取运行时间和占用内存的这种跑代码的方式评估算法执行效率是正确的，很多时候它叫：事后统计法。但是这个方法有局限性。 1、测试结果非常依赖环境。 2、测试结果受数据规模影响很大。 所以需要一个不用具体的测试数据来测试，就可以粗略地估计算法执行效率的方法。 时间复杂度分析： 1、只关注循环执行次数最多的一段代码。 2、加法法则：总复杂度等于量级最大的那段代码的复杂度。 3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。 参考资料来源：百度百科--时间复杂度