algorithm - 如何找到特定程序的运行时间？

Question

对于下面的每个过程，令 T (n) 为运行时间。求出T(n)的阶数(即找到 f(n) 使得 T (n) ∈ (f(n))。

过程 Fum(int n):

for i from 1 to n do    
 y ← 1/i
 x ← i
 while x > 0 do    
  x ← x − y 
 end while
end for

我知道如何查找简单函数的运行时间，但由于这是一个嵌套循环，其中内循环依赖于外循环中的变量，所以我遇到了麻烦。

Answer 1

应该是 1+4+9+...+n^2 = n(n+1)(2n+1)/6 ，或简单地 O(n^3) ，对于这种情况。

对于 for 中的每一步-循环，它将运行 i^2 while 的次数.鉴于 x=i;y=1/i; , 需要 i^2 (作为 x=y*i^2 )次 x到达x<=0通过递减步骤x=x-y .

对于 i , 它将是 1,2,...,n ，将它们相加，你会得到 1+4+9+...n^2 = n(n+1)(2n+1)/6 .