algorithm - 这个函数在 C 中的时间复杂度是多少？

Question

我想用 C 计算这个函数的复杂度。这是一棵普通的树

struct nodeG {  
  int key;
  struct nodeG *left_child;
  struct nodeG *right_sib;
};

int aux (NodeG u) {
    int current = 1;                                                // O(1)
    int childs = 0;                                                 // O(1)
    while (u) {                                                     // O(k)
        if (u-> left_child)                                         // O(1)
            childs += aux (u-> left_child);                         // O(1)
        if (u->right_sib && current && u->key < u->right_sib->key)  // O(1)
            current = 0;                                            // O(1)
        u = u -> right_sib;                                         // O(1)
    }
    return current + childs;                                        // O(1)
}

Answer 1

考虑到所有递归调用，该函数对树中的每个节点执行 O(1) 次操作，因此总运行时间为 O(n)，其中 n 是节点数。

更详细地说，该函数为每个节点的最左边的子节点调用一次。 while 循环然后遍历它的所有兄弟。所以循环内部每个节点执行一次，或者总共执行n次。除了循环和递归调用，其余的语句都是 O(1)。所以这最终会花费 O(n) 的时间。