尝试找到递归算法的时间效率时遇到问题

Question

我正在学习算法的时间效率，并且一直坚持尝试分析递归算法。我目前有一个算法，基本上只是遍历二叉搜索树并将每个节点放入一个数组中。

placeIntoArray(root, array[]a, int i) {
    if (root.left != null) {
       i = placeIntoArray(root.left, a, i);
    }
    a[i] = root;
    i++;
    if (root.right != null) {
       i = placeIntoArray(root.right, a, i);
    }
    return i;
}

如果我不得不猜测我会认为它在 O(n) 的 class 中，因为它只是触及将它放入数组中的每个节点，但我不确定如何分析它正确..任何帮助将不胜感激

Answer 1

对于大小为n的数组，问题的时间复杂度为T(n) = T(number of the elements in the root.left) + T(number of the elements in the root.right) + c，c为常量。在两种极端情况下，T(n) = 2T(n/2) + c（完全平衡）意味着 T(n) = Theta(n) 或 T(n) = T(n-1) + T(1) + c（完全不平衡）意味着 T(n) = Theta(n)。如果考虑其他情况，您会发现 T(n) = Theta(n)。