如果我们发现没有。一个数字的因素，我们可以使用以下高效循环。 for(i=1;i<=sqrt(n);i++)，其中 n 是要找到其因子的“否”。这个循环的复杂度为 O(n)。
以下代码片段的时间复杂度是多少？ (假设 log(x) 以 2 为底返回对数值)。 O(n^2) 还是 O(n logn)？ (我假设 log n 是循环除以二时的复杂度。即 i/=2)
void fun()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=log(i);j++)
printf("hello world");
}
最佳答案
您的代码中实际打印的“Hello world”数量是:
然后您可以使用 Srinivasa Ramanujan approximation日志(n!):
得到整个代码的实际复杂度，即O(n logn)
关于algorithm - 循环运行日志时间时的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29556801/