c - 计算三叉树中具有给定键的所有节点的时间复杂度？

Question

我需要找出程序中某个函数的时间复杂度。它搜索具有给定键的三元树的所有内部节点。这棵树是随机填充的。我想我已经设法编写了代码，但我不知道如何计算复杂性。

这是树的功能和结构:

typedef struct _no
{
    int chave; 
    struct _no *F[3]; 
} TipoNo;

typedef TipoNo *TipoArvore;

int noSubTree (TipoArvore t, int x){
    int n;
    if (t == NULL){
        return 0;
    }
    else{
        if(t->F[0] == NULL && t->F[1] == NULL && t->F[2] == NULL ){
             return 0;
        }
        else if(t->chave == x) {                 
          return 1 + noSubTree(t->F[0], x) + 
                     noSubTree(t->F[1], x) + 
                     noSubTree(t->F[2], x);
        }
        else {
          return 0 + noSubTree(t->F[0], x) +
                     noSubTree(t->F[1], x) +
                     noSubTree(t->F[2], x);
       }
    }
 }

如果有人能向我解释应该如何完成，我将不胜感激。

Answer 1

思考这个问题的一种方法是思考

• 每个节点被访问了多少次，以及
• 每次访问节点完成多少工作。

请注意，您的代码每次访问节点时的运行时间为 O(1) - 它只是触发更多的递归调用，并可选择将结果加一。您还只访问每个节点一次。每个节点只调用其子节点上的函数，因此最终将到达所有节点，并且由于所有调用都是向下的并且从不重叠，因此不会访问节点两次。

因此，总时间复杂度为 Θ(n)，其中 n 是树中节点的总数。

作为一个完全不相关的旁白:由于您是用 C 语言编写这段代码，因此您可以将一些案例浓缩在一起。例如，看看这些代码行:

if(t->chave == x) {                 
    return 1 + noSubTree(t->F[0], x) + 
               noSubTree(t->F[1], x) + 
               noSubTree(t->F[2], x);
}
else {
   return 0 + noSubTree(t->F[0], x) +
              noSubTree(t->F[1], x) +
              noSubTree(t->F[2], x);
}

在 C 中，如果两个参数相等，则逻辑运算符 == 的计算结果为 1，否则为 0。因此，您可以将这些案例浓缩成这样:

return (t->chave == x) + noSubTree(t->F[0], x) +
                         noSubTree(t->F[1], x) +
                         noSubTree(t->F[2], x);

希望这对您有所帮助!