緊（Θ）綁定

有人可以向我解釋這個嗎？像這樣的：緊（Θ）綁定

給出一個函數：

for k = 1 to lg(n) 
    for j = 1 to n 
    x=x+1

我將如何分析緊（Θ）綁定？

來源

2010-05-24 tomwu

你的功能是Θ（日誌ñ·Ñ）：外循環被重複日誌Ñ倍和內環Ñ倍（對於外for的每次迭代），所以x=x+1是執行日誌n·n次總共。而且由於重複次數是固定的，所以下限和上限是相同的。

來源

2010-05-24 22:16:02 Gumbo

我還有一個問題，如果j = 1到k2的內循環爲，我將如何處理這種情況。我知道答案是n^3。但我將如何證明這樣的事情我該如何將它應用於類似的東西？ – tomwu 2010-05-25 00:26:25

@tomwu：有兩種不同的成本度量：統一成本度量，每個基本操作度量一個單位;以及基於實際計算成本來衡量每條指令的對數度量。雖然後者更精確，但前者通常是首選，因爲它顯然更容易處理。因此，第一步是對每個陳述的成本進行評估。其餘的是數學：連續的操作被添加並且重複的操作相乘。對於我們的例子，我們可以說log * n *（* n *（3）），而每對圓括號表示我們算法中的'for'主體。 – Gumbo 2010-05-25 07:05:37

3從'x = x + 1'中的三個操作派生而來：讀* x *，加1並寫回* x *。所以我們的函數是Θ（log * n * * * n * 3）。但靜態3可以省略，其餘是Θ（log * n * * * n *）。 – Gumbo 2010-05-25 07:09:09

回答

相關問題