1

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

这是树的函数和结构：

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);
       }
    }
 }

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

4

2 回答 2

0

noSubTree()- 以根为起点 - 命中树的每个节点，但每个节点只命中一次，因此该函数的复杂度为 O(n)。

如果您想找到搜索的复杂性，这是一个更大的问题。在平衡二叉树上的搜索具有 O(log 2 (n)) 的复杂度。在平衡三叉树上的搜索将是 O(log 3 (n))。在最坏的情况下，对不平衡树的搜索将不得不遍历每个节点，因此复杂度为 O(n)。

于 2013-11-01T01:31:39.240 回答
0

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

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

请注意，您的代码每次访问节点时都会执行 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);

希望这可以帮助！

于 2013-11-01T01:08:59.010 回答