Блог

Я хочу решить этот вопрос, но я не уверен, прав я или нет. Я нашел 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));
}
 

Ваша 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
 

Легко видеть, что решение этого рекуррентного соотношения T(i) = i для всех i > 0 , так T(i) ∈ O(i) что .

Ваша вторая функция funcQ2 не имеет входных данных, и, предполагая, что n это константа, ее сложность тривиально равна O (1) . Если, с другой стороны, вы предполагаете n , что это входной параметр, и хотите измерить временную сложность относительно n , это будет O(n^2) так, поскольку вы вызываете fact(i) внутри цикла (стандартный арифметический ряд).