c++ - 以下代码的复杂性是多少？

Question

下面这段代码的复杂度是多少？

for (int i = 1; i * i <= n; i++)
{
   if (n%i == 0)
     //do anything
}

Answer 1

循环运行√n次，每次满足条件是i一个因素n——后者是一个不平凡的条件，需要仔细分析。它取决于 的素数分解n。例如，如果n是素数，则条件只为真一次，对于i == 1，并且永远不会再为真。