循环的复杂性是什么
for (int i = 0; i < n; i++)
{
for (int j = 0; j < log(i); j++)
{
// do something
}
}
据我说，内部循环将是运行log(1)+log(2)+log(3)+...+log(n)时间，那么如何计算其复杂性？
因此，您有一笔款项log(1) + log(2) + log(3) + ... + log(n) = log(n!)。通过使用斯特灵公式和事实，即ln(x) = log(x) / log(e)人们可以得到
log(n!) = log(e) * ln(n!) = log(e) (n ln(n) - n + O(ln(n)))
这给出了与O(n ln(n))其他答案相同的复杂度（对所涉及的常数有了更好的理解）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句