在這種情況下，「常量」是什麼意思？

Question

我目前正在讀算法導論書，我有一個問題關於分析的算法：

的合併排序的計算成本是根據書çLG n和它說，

我們將c限制爲一個常數，以便字大小不會隨意增大（如果字的大小可以任意增長，我們可以將大量數據存儲在一個字中，並在一段時間內對其進行操作）

我不明白「常量」的含義。誰能解釋清楚這是什麼意思？

Answer 1

算法研究中的計算複雜性涉及尋找提供算法需要多少時間（或空間）的上限和下限的函數。回想一下高中的基本代數，你學習了一條線的一般點斜率公式嗎？該公式y = mx + b提供了兩個參數，m（斜率）和b（y截距），它們完全描述了一條直線。那些常數（m，b）描述了線的位置，而較大的斜率表示線更陡。

算法複雜度只是一種描述算法花費多長時間（和/或需要多少空間）的上限（也可能低於下限）的方法。使用big-O（和big-theta）符號，您可以找到爲算法成本提供上限（和下限）的函數。常數只是移動曲線，而不是改變曲線的形狀。

Answer 2

我們限制C到是一個常數，使得字的大小不arbirarily增長（如果字的大小可以隨意增長，我們可以存儲大量的數據在一個字，在固定時間上的所有操作）

在物理計算機上，機器字有一些最大尺寸。在32位系統上，這可能是32位，而在64位系統上，它可能是64位。對機器字的操作（通常）被假定爲花費時間O（1），即使它們同時在很多位上操作。例如，如果您在機器字上使用按位或或按位AND，則可以將其視爲在一個單位時間內執行32或64個並行OR或AND操作。

當試圖建立一個計算系統的理論模型時，有必要假定一個機器字的最大尺寸的上限。如果你不這樣做，那麼你可以聲稱你可以執行諸如「在時間O（1）中計算n個值的OR」或者「在時間O（1）中加上兩個任意精確數字」的操作，「操作你實際上不能在真正的電腦上做。因此，通常假定機器字有一些最大尺寸，所以如果你想要計算n值的OR，你仍然可以這樣做，但是你不能通過將所有值打包到一臺機器單詞並執行單個彙編指令來獲得結果。

希望這會有所幫助！