Временная сложность при l oop с рекурсией

Question

   void call(int n)
    {
         for (int j=1;j<=n;j++)
         {
           call(n/2);
          }
     }

   void main()
    {
      int i;
      for (i=1;i<=n;i++)
       {
          call(i);
       }
     }

За сложность этого времени l oop. Правильно ли мыслительный процесс? В основной функции l oop равно O (N). В функции вызова l oop - это O (N), рекурсия которого равна n / 2, поэтому O (logN) с базой 2. Таким образом, общая сложность времени в основном составляет O (N) * [ O (N) * O (LogN)] = O (N ^ 2 Log N)?

Answer 1

вы можете использовать дерево рекурсии, чтобы выяснить количество вызовов, а порядок функции рекурсии равен числу узлов в дереве рекурсии (листья вызова (n / 2), который не отображается):

, поэтому для вычисления количества всех узлов вы можете рассчитать суммирование и оценить порядок (используя последовательность геометрических фигур c по формуле для вычисления суммирования):

Порядок основного l oop меньше , поэтому основной l oop порядок