关闭。这个问题是 opinion-based 。它目前不接受答案。












想改善这个问题吗?更新问题,以便可以通过 editing this post 用事实和引文来回答。

4年前关闭。



Improve this question




我在计算机科学教科书中看到以下内容,

algorithm - 为什么计算机科学中的对数被假定为以 2 为底的对数?-LMLPHP

......所以,我想知道是否有人可以向我解释原因。

最佳答案

计算机科学中出现对数的最常见方式之一是将某个数组重复地分成两半,这在二分搜索、归并排序等分而治之算法中经常发生。在这些情况下,您可以除以的次数在你深入到单元素数组之前,长度为 n 的数组是 log2 n。

对数产生的另一种非常常见的方式是查看数字的位。用二进制写出一个数字,数字 n 大约使用 log2 n 位。像基数排序这样的算法有时一次只工作一点,通常会产生这样的日志。其他算法(如二进制 GCD 算法)通过除以 2 的幂来工作,因此最终会产生 float 的对数因子。

物理学、数学和其他科学中的对数经常出现,因为您正在处理随时间增长的连续过程。在这些上下文中出现自然对数​​是因为某个过程随时间的“自然”增长率由 ex 建模(对于“自然”增长率的某些定义)。但在计算机科学中,指数增长通常是离散过程(如上述分而治之算法)或二进制值操作的结果。因此,我们通常使用 log2n 作为对数函数,因为它出现得如此频繁。

这并不是说我们总是在 CS 中使用以 2 为底的对数。例如,由于存在斐波那契数,AVL 树的分析通常涉及以黄金比例 φ 为底的对数。许多随机算法确实以某种方式涉及 e,例如快速排序的标准分析,它涉及调和数,因此连接回自然对数。这些是增长率由其他东西(斐波那契数或指数函数)建模的过程示例,因此我们在那里选择了不同的对数基数。只是使用二进制数或将事物一分为二是很常见的,以二为底的对数最终成为默认值。

在许多情况下,您选择的基础甚至都无关紧要。例如,在 big-O 表示法中,所有对数都是渐近等价的(它们仅相差一个乘法常数因子),因此在编写 O(n log n) 或 O(log n) 之类的内容时,我们通常甚至不指定底数)。

关于algorithm - 为什么计算机科学中的对数被假定为以 2 为底的对数?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/42568658/

10-14 01:01