Как я могу быстро определить сложность кода ниже и в любом другом коде?

Question

#include <stdio.h>
int f(int (*d)[2], int n)
{
      int p = 0, cnt;
      for (int i=2; i*i <= n; ++i)
      {
             for (cnt = 0; n % i == 0; cnt++, n /= i) {}
             if (cnt == 0)
                  continue;
             d[p][0] =  i;
             d[p++][1] = cnt;
      }
      if (n > 1)
      {
             d[p][0] = n;
             d[p++](l] = 1;
      }
      return p;
}

Итак, насколько я понимаю, когда я ищу сложность, я ищу петли.Первый цикл тривиален.Это дает нам O(sqrt(n)), но есть второй цикл, который уменьшает n, я не очень понимаю этот момент.Эксперименты показывают, что сложность составляет O(log(n)).

Answer 1

Говоря о втором цикле: n% i == 0;и n = n / i;если мы зациклим цикл for, мы получим в первой итерации n = n / i / i .... в итерации k мы получим n / (i ^ k), и это прекратится, когда n% i!= 0;скажем, n / (i ^ k) == 1, так что 1% i == 1! = 0, поэтому из n / (i ^ k) == 1 мы получим k = log (n) в базе i, что означаетжурнал (п)