简单的时间复杂度问题

Question

我需要知道这两段代码的复杂度。

public static int Sum(int x, int y){ 
return y*(y+1)/2 - (x-1)*x/2;
}

public static int RecSum(int x, int y){ 
if (x < y+1)
    return x + RecSum(x+1, y);  
else
    return 0;    
}

我认为 Sum 是 O(n^2)，RecSum 是 O(n)。

我说得对吗？

Answer 1

如果您看一下 Sum()，当输入改变时，循环次数如何改变？无论输入如何，Sum() 只执行 1 次计算。换句话说 - 无论输入如何，执行时间都是恒定的。因此你有 O(1).

RecSum() 调用自身。次数取决于 y, x 之间的差异。因此，如果该差异加倍，则执行时间加倍。所以你有 O(n)

也许这也有用

简单的时间复杂度问题

Simple time-complexity problems

java

time-complexity