为什么计算机科学中的对数被认为是基数为2的对数？
And*_*ndy 9 algorithm math logarithm
我在计算机科学教科书中看到了以下内容,
......所以,我想知道是否有人可以向我解释原因.
tem*_*def 20
在计算机科学中出现对数的最常见方法之一是将一些数组重复分成两半,这通常发生在二元搜索,mergesort等分而治之的算法中.在这些情况下,你可以划分的次数在进入单元素数组之前,长度为n的数组是log 2 n.
另一种非常常见的对数方式是通过查看数字的位.以二进制形式写出数字大约使用log 2 n位作为数字n.像基数排序这样的算法有时会一次一点地工作,这通常会产生这样的日志.其他算法(如二进制GCD算法)通过将功率除以2来工作,因此最终会出现浮动的对数因子.
物理,数学和其他科学中的对数经常出现,因为你正在处理随时间增长的连续过程.自然对数出现在这些情境中,因为某些过程随时间的"自然"增长率由e x建模(对于"自然"增长率的某些定义).但是在计算机科学中,指数增长通常是由于离散过程的结果,如上面描述的分而治之算法或操纵二进制值.因此,我们通常使用log 2 n作为对数函数,因为它只是频繁出现.
这并不是说我们总是在CS中使用基数为2的对数.例如,AVL树的分析通常涉及对数,其基数是由于Fibonacci数的存在而的黄金比率φ.许多随机算法确实以某种方式涉及e,例如快速排序的标准分析,其涉及谐波数并因此连接回自然对数.这些是增长率由其他东西建模的过程的例子 - 斐波纳契数或指数函数 - 因此我们在那里选择不同的日志基数.只是因为使用二进制数或将事物分成两半而言是足够常见的 - 两个对数最终成为默认值.
在许多情况下,您选择的基数甚至不重要.例如,在big-O表示法中,所有对数都是渐近等价的(它们只相乘乘法常数因子),所以我们通常甚至在写O(n log n)或O(log n)时都不指定基数. ).