algorithm - 算出 f(n)，即每个过程所需的单位时间操作的确切数量，作为输入大小 n 的函数

Question

我有这 2 个问题 - 我相信其中一个问题之前已发布 - 但没有人回答。我想我已经正确回答了第二个......

有什么建议吗？

计算出 f(n)，即每个过程所需的单位时间操作的确切数量输入大小 n 的函数

(i) for i<-1 to n do
 for j<-1 to 2n-i do
//a unit cost operation
  ------------------------------ (i) this is i the one i need some help on.
(ii) for i <-1 to n do
 for j <- 2 to (n+i) do
// a unit cost operation

for i: 1 to n do:
 for j: 2 to n + i do:
  unit

现在，假设 n=1

 i=1; j: 2 to 2 = 1 times
 total: 1 units

  n=2

i=1; j: 2 to 3 = 2 times
i=2; j: 2 to 4 = 3 times
 total: 2 + 3 = 5 units

 n=3

i=1; j: 2 to 4 = 4 times
i=2; j: 2 to 5 = 5 times
i=3; j: 2 to 6 = 6 times
total: 4 + 5 + 6 = 10 units

  Pattern being f(n) = n^2 +1 , is that right?

Answer 1

对于您提到的案例(案例 (i))，您可以使用 Arithmetic Progressions

在这种情况下，第一项=2*n-1，最后一项是n，所以所有项的总和是

S=n/2*(n+2*n-1)=O(n^2)

对于情况 II，第一项=(n+1-1)=n，最后一项=(n+n-1)=(2*n-1)，所以 Sum，S 等于，

S=n/2(第一项+最后一项)=n/2*(n+2*n-1)=O(n^2)

您一定已经观察到 (i) 和 (ii) 的 S 是相同的。