Итак, я должен доказать, что время работы InOrder - рекурсивной версии - O (n). Насколько мне известно, эту проблему можно решить, доказав, что мы не go пересекаем края более двух раз. Однако ко мне обратились с идеей, которая предлагает использовать индукцию, в которой я не уверен, возможно ли это сделать:
«Мы используем индукцию для количества узлов, время работы которых равно O ( n). Основание легко доказать. Глядя на двоичное дерево с n узлами, предположим, что левое дерево имеет k узлов, а правое - n-1-k узлов, из предположения индукции, время работы InOrder на левое дерево - это O (k), а время работы на правом дереве - O (n-1-k). Затем мы можем сделать вывод, что время работы составляет O (n) "
Правильно ли это подходить? Конечно, перед заключением должен быть еще один шаг, вопрос в том, можно ли это решить? Можно ли вообще использовать индукцию таким образом?
для справки, вот алгоритм:
Inorder(node):
if root.left != null:
Inorder(root.left)
print(root.value)
if root.right != null:
Inorder(root.right)