爲什麼計算機科學中的對數被假定爲基數爲2的對數？

Question

我看到一個計算機科學課本下面，

...所以，我想知道，如果有人可以給我解釋爲什麼。

Answer 1

對數在計算機科學中出現的最常見方法之一是通過將一些數組重複分割成一半，這通常發生在二進制搜索，合併排序等分而治之算法中。在這些情況下，次，你可以劃分一個長度爲n的數組，然後再考慮單元素數組。

另一種很常見的對數出現方式是通過查看數字的位。用二進制表示一個數字大概用於編號n的n位。像基數排序這樣的算法，有時候一次只能工作一次，通常會產生像這樣的日誌。其他算法（如二進制GCD算法）通過分解兩個冪來工作，並因此最終以漂移的對數因子結束。

物理學，數學和其他科學中的對數經常出現，因爲您正在處理隨時間而變化的連續過程。自然對數出現在這些背景下，因爲某些過程隨時間推移的「自然」增長率是通過模擬e ^x（對於「自然」增長率的一些定義）來建模的。但是在計算機科學中，指數增長通常是由於像上述分而治之算法這樣的離散過程或操縱二進制值而產生的結果。因此，我們通常使用log作爲對數函數，因爲它經常出現。

這並不是說我們總是在CS中使用基數爲2的對數。例如，AVL樹的分析通常涉及以黃金比率爲基礎的對數，由於斐波納契數的存在，其基數爲φ。許多隨機算法在某種程度上確實涉及到e，例如快速排序的標準分析，它涉及諧波數量，因此連接回自然對數。這些都是增長率由別的東西 - 斐波那契數或指數函數 - 建模的過程的例子 - 所以我們選擇不同的日誌庫。只是用二進制數字處理或將事物分成一半而非常普遍 - 兩個對數最終成爲默認值。

在許多情況下，它甚至不關心你選擇的基地。例如，在大O符號中，所有對數都是漸近等價的（它們只是乘以一個常數因子），所以在寫O（n log n）或O（log n）時，我們通常甚至沒有指定基數）。