Как подсчитать временную сложность этой рекурсивной функции?(БСТ) - PullRequest
0 голосов
/ 18 мая 2018

У меня есть некоторые проблемы с подсчетом временной сложности функции, которую я написал для своей задачи.

Эта функция является рекурсивной и подсчитывает, сколько листов со значением больше 10 в бинарном поискеДерево.Вот функция:

int count_leaf(node* root)
{
  static int count = 0; 
  int call; 
  if (root == NULL) 
   {
     return 0;
   }
  call = count_leaf(root->left);
  if (root->left == NULL && root->right == NULL && root->data > 10)
   {
     count++;
   }
  call = count_leaf(root->right); 
  return count;
}

Какой самый правильный и правильный способ подсчитать сложность времени для этой функции?

Ответы [ 3 ]

0 голосов

Сложность на самом деле O(n), так как вам нужно посетить все узлы.Это лучше, чем O(n*log n), связанный с двоичными деревьями.Это также асимптотически оптимально.

Доступ к дочерним узлам осуществляется непосредственно из родительского узла, а не из корня, и так далее для каждого дочернего узла, и доступ к дочерним узлам таким образом является операцией с постоянным временем.По завершении обхода все узлы n были посещены.

0 голосов
/ 19 мая 2018

Один простой способ экспериментально измерить сложность реализации алгоритма - поместить счетчик (и) в начало функции или цикла (ов), которые используются для итерации.Для вашего примера что-то вроде следующего:

int test_count = 0;

int count_leaf(node* root)
{
  static int count = 0; 
  int call; 

  ++test_count;

  // ...

}

Затем распечатайте значение test_count после запуска теста.Если вы проведете эксперимент с различными наборами тестов (сделайте каждый набор в два раза больше предыдущего, чтобы сделать различия очевидными), вы получите хорошее представление о том, является ли алгоритм O (1), O (n), O (n ^2) и т. Д.

Альтернативой является использование простого таймера для измерения продолжительности тестовых прогонов.Сравните время запуска алгоритма с несколькими наборами данных, размер которых удваивается.Разница во времени обработки каждого набора данных даст вам представление о сложности вычислительных алгоритмов.См. Пару примеров «Алгоритмы» Седжвика, 4-е издание, раздел 1.4.

Очевидно, что это не доказательства и могут быть неприемлемы для большинства ответов на домашние задания, но это может помочь вам убедиться, что вы правильно поняли ответ на домашнее задание.

0 голосов
/ 18 мая 2018

Он касается каждого узла дерева ровно один раз, поэтому будет n вызовов, что делает его O(n).

...