對數與統一成本標準之間的區別

Question

我在理解對數（Lcc）和統一（Ucc）成本標準之間的差異以及如何在計算中使用它時遇到了一些問題。

可能有人請解釋兩者或許之間的差異表明如何計算的複雜性對於像A + B * C

（是的，這是一個任務的一部分=））

THX問題任何幫助！

/Marthin

Answer 1

統一成本標準分配一個恆定成本每臺機器操作，而不管所涉及WHILE對數成本標準比特數的分配到每個機操作成比例的比特的數目的費用涉及

Answer 2

，我認爲你應該做一些研究，大O符號... http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

如果有說明書的一部分，你發現很難編輯你的問題。

Answer 3

問題大小影響複雜 由於複雜性依賴於 問題的大小，我們定義複雜成爲問題大小的函數 定義：設T（n）表示的複雜性 被施加到所涉及的算法問題 大小n。 問題實例（I）的大小（n）是用於表示 實例的（二進制）位數 。所以問題的大小是實例的二進制描述的長度 。 這就是所謂的對數費用標準

單位成本的標準 如果假設： - 每一臺計算機指令需要一個時間 單位， - 每個寄存器是一個存儲單元 - 而且一些總是在寄存器適合 然後你可以使用輸入的數量作爲 問題的大小，因爲輸入的長度（以位爲單位） 將是一個常數倍的輸入。

Answer 4

統一成本標準假設每條指令都需要一個單位時間，並且每個寄存器都需要一個單位的空間。

對數成本標準假設每條指令都採用對數數量的時間單位（相對於操作數的長度），並且每個寄存器都需要對數個單位的空間。

簡而言之，這意味着統一成本標準計算操作次數，而對數成本標準計算位操作次數。

例如，假設我們有一個8位加法器。

如果我們使用統一的成本標準來分析加法器的運行時間，我們會說加法需要一個單位時間單位;即T（N）= 1。

如果我們使用對數成本標準來分析加法器的運行時間，我們會說加法需要lg⁡n個時間單位;即T（N）= lgn，其中n是你必須根據時間複雜度添加的最差情況數（在這個例子中，n將是256）。因此，T（N）= 8。

更具體地說，假設我們將256加到32中。爲了執行加法，我們必須在1s列，2s列，4s列等等中添加二進制位（列表示位位置） 。數字256需要8位。這就是我們分析對數的原因。 lg256 = 8。所以要添加這兩個數字，我們必須在8列上進行加法。對數成本標準指出，這8個加法計算中的每一個都需要一個單位時間。統一的成本標準認爲，整套8個加法計算需要一個單位時間。

也可以根據空間進行相似分析。登記冊要麼佔用一定數量的空間（在統一的成本標準下），要麼佔用對數的空間（在統一的成本標準下）。