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