c-查找时间复杂性，何时将它们相加/相乘

Question

如何找到嵌套循环的时间复杂性？此外，如何找到由多个函数组成的程序的时间复杂性？

基本上，我很困惑什么时候该加/乘时间复杂性。

#include <stdio.h>
long pascal(int, int);
int main()
{
int n,m,k,j;
printf ("Enter the height for Pascal's Triangle: ");
scanf("%d", &n);
for(k = 0; k<n; k++)
{
for(j = 0; j < n-k; j++)
{
printf(" ");
}
for(m = 0; m <= k; m++)
{
long f = pascal(k, m);
printf("%ld ", f);
}
printf("n");
}
return 0;
}
long pascal(int n, int i)
{
if(n == i || i == 0)
return 1;
else
return pascal(n-1, i) + pascal(n-1, i-1);
}

这是我用来打印Pascal三角形的代码。如何发现其时间复杂性？

Answer 1

• 您的第一个循环-for(k = 0; k<n; k++)运行Θ(n)
• 你的第二个循环-for(j = 0; j < n-k; j++)作为一个算术级数运行，所以它是Θ(n^2)
• 您的第三个循环作为第二个循环运行，因此Θ(n^2)
• 您的pascal函数运行O(2^n)，因为它是由两部分组成的递归函数：pascal(n-1, i) + pascal(n-1, i-1);您可以在该链接中看到完整的解释：https://stackoverflow.com/a/360773/13292734

结论：

• 如果没有pascal函数，时间复杂度为Θ(n^2)
• 但发生的时间最长的是函数pascal，其时间复杂度为O(2^n/sqrt(n))。您可以在这里看到为什么是O(2^n/sqrt(n))而不是O(2^n)：https://stackoverflow.com/a/26229383/13292734
• 因此时间复杂度为：O(n^2)*(2^n/sqrt(n))。或者你可以说：O(n^2)*(2^n)这也是正确的