算法的執行時間T（n）是多少？

-3

您能否向我解釋2種算法的執行時間T（n）是多少？假設執行時間T（N）=的＃處決（A：= A + 1）算法的執行時間T（n）是多少？

算法1：

for i ← 1 to n do 
     for j ← 1 to i do 
      for k ← j to i+j do 
        a ← a + 1 
      end for 
     end for 
end for

算法2：

for i ← 1 to m do 
     for j ← 1 to i^2 do 
      for k ← 1 to j do 
        a ← a + 1 
      end for 
     end for 
end for

來源

2010-01-09 user247133

作業？....... – 2010-01-09 17:10:10

家庭作業？如果是這樣，標記它。 – lmsasu 2010-01-09 17:10:13

執行時間T（n）的可以通過計算髮生的原子操作的數量來找到（例如，將值a+1指定爲a）。在這種情況下，計算數字操作並不那麼困難，因爲在每個算法中，只有一個操作，其執行次數由循環的固定範圍控制。因爲這是家庭作業（或者聽起來像是這樣），我不打算執行計算，但是你是否足夠了解嵌套循環以確定每個執行體的執行次數？

來源

2010-01-09 17:12:53 danben

對於這些算法，您應該嘗試以n（或m，在算法2中）的形式得出一個表達式。對於這些算法，該表達式將是一個多項式。該多項式的階數實際上是該算法的O（n）複雜度。現在有了這個提示，你應該能夠完成作業。

來源

2010-01-09 17:15:58 Tarydon

他不是在計算複雜度O（n），而是計算執行時間T（n）。 – danben 2010-01-09 17:18:29

@danben：我的錯。 – Tarydon 2010-01-09 17:20:56

這裏是你如何處理這些：

對於第一，弄清楚有多少次最內層循環執行作爲i和j功能。致電此號碼f(i, j)。然後我們注意到

sum(i = 1 to n) sum(j = 1 to i) f(i, j)

將是所需的答案。那麼這是計算這個總和的問題。我會給你一個提示：答案涉及知道如何總結連續的正方形和連續的整數。（我100％確定你的教授在課堂上對此有所瞭解。）

對於第二種，類似的方法。對於這一個，你需要知道連續四次冪的總和，再次是連續的平方和。

我有這兩個答案;如果你想，發佈一個解決方案，我會檢查我的並提供意見。

來源

2010-01-09 17:27:52 jason

算法的執行時間T（n）是多少？

回答

相關問題