计算大O

Question

我试图计算这个函数的大O，它是(数据结构)二进制搜索树的镜像。但我不确定计算是否正确。你能解释一下大爆炸会是什么吗？

void mirror(NODE *root){
    if (root) {
        mirror(root->left);
        mirror(root->right);
        NODE *temp = root->left;
        root->left = root-> right;
        root->right  = temp;
    }
    return;
}

我认为它是O(n)，因为函数将递归地运行n次，这取决于树中有多少元素。

Answer 1

除函数调用之外的所有操作都是固定时间操作：

void mirror(NODE *root) {
    if (root) {                    // O(1)
        mirror(root->left);
        mirror(root->right);
        NODE *temp = root->left;   // O(1)
        root->left = root-> right; // O(1)
        root->right = temp;        // O(1)
    }
    return;                        // O(1)
}

递归调用将访问所有节点一次(深度优先遍历)，因此如果表示树中的节点数，则时间复杂度为O()。