这些函数的大 O 表示法

Question

我想解决这个问题，但我不确定我是否正确。我发现 O(n^2-n)=O(n^2)

double fact(long i)
{
if (i==1 || i==0) return i;
else return i*fact(i-1);
}

funcQ2()
{
for (i=1; i<=n; i++)
sum=sum+log(fact(i));
}

Answer 1

你的fact函数是递归的，所以你应该先写出时间复杂度对应的递归关系T(i):

T(0) = 1             // base case i==0
T(1) = 1             // base case i==1
T(i) = T(i-1) + 1    // because fact calls itself on i-1 and does one multiplication afterwards

很容易看出这个递归关系的解对所有i > 0都是T(i) = i，所以T(i) ∈ O(i).

你的第二个函数 funcQ2 没有输入，假设 n 是一个常数，它的复杂度是 O(1)。另一方面，如果您假设 n 是一个输入参数，并且想要测量关于 n 的时间复杂度，那么它将是 O(n^2)，因为您正在调用 fact(i) 在循环内（标准算术级数）。