算法添加

Question

對於下面的算法，我需要以下幫助。

1. Algorithm Sum(m, n) 
   //Input: A positive integer n and another positive integer m ≤ n 
   //Output: ? 
   sum = 0 
   for i=m to n do 
   for j=1 to i do 
   sum = sum + 1 
   end for j 
   end for i 
   return sum 
   

   我需要幫助搞清楚什麼計算？加法總數的公式是什麼？sum =（sum + 1）。

   我有算法計算m和n之間的所有正整數，包括m和n。 添加次數公式爲。 M + M + 1 + ...... + N

Answer 1

我不明白你的問題......看來你問的東西，但你也自己已經提供了答案......反正這裏是我的答案對這些問題...

對於Q1，看來你是要求輸出和迭代的總數（這是summation(m..n) = (n+m)(n-m+1)/2）

對於Q2的數量，看來你也是問了多少次已經執行了比較，這是n-1次。

爲了解決復發T（n）=在第（n-1）+ C其中，a，c爲常數，通過 的n-2，n-3重複取代...直到1，可以看到T(n) = O(n)

PS：如果是作業，也許你做了，因爲你似乎已經有自己的答案了，我強烈建議你嘗試通過一些具體的案例對於Q1。對於第二季度你應該嘗試理解幾種方法來計算出遞歸關係，替代方法可以用來解決這種容易的關係，其他許多人可能需要使用master theorem。

另外你應該讓自己明白爲什麼Q2的複雜性實際上和普通的循環迭代方法一樣簡單。