N叉树的插入和搜索复杂度是什么？

Question

我将在C#中实现一棵N-1ry树。我想知道如何计算以下方法的复杂度。这是我的代码:

结构:

public class Node
{
    public int Value { get; set; }
    public Node Children { get; set; }
    public Node Sibilings { get; set; }

}

这是一种搜索方法:

public Node search(Node root, int data)
{
    if (root == null)
        return null;

    if (data == root.Value)
        return root;

    Node t = search(root.Children, data);
    if (t == null)
        t = search(root.Sibilings, data);
    return t;
}

这是插入的一种方法：

public void Add(int[] data)
{
    Node temp = null;
    temp = search(ROOT, data[0]);

    if (temp == null)
        temp = new Node(data[0]);

    if (this.ROOT == null)
        ROOT = temp;
    Node parent = temp;

    for (int j = 1; j <= this.NoOfChildrens; j++)
    {
        // for first child
        if (j == 1)
        {
            parent.Children = new Node(data[j]);
            parent = parent.Children;
        }
        //for all other childs
        else
        {
            parent.Sibilings = new Node(data[j]);
            parent = parent.Sibilings;
        }

    }

}

程序入口点:

static void Main(string[] args)
{
    NAryTree naryTree = new NAryTree(3);

    // 1st element in each row is node Value,>=2nd....=>value of child

    int[][] data = { new int[] { 1, 2, 3, 4 }, new int[] { 2, 1, 6,0 }, new int[] { 3, 8, 9, 10 }, new int[] { 4, 0, 0, 0 } };

    naryTree.Add(data[0]);
    naryTree.Add(data[1]);
    naryTree.Add(data[2]);
    naryTree.Add(data[3]);
    naryTree.Add(new int[] {10,3,6,4});

    naryTree.preorder(naryTree.ROOT);
    Console.ReadLine();
}

这些方法的大O复杂度是什么？

- Qasim Ahmed

---

你只展示了一些代码，但是在Add方法中缺少重新平衡子节点的代码提示O(total_number_of_nodes)是最佳选择（根据其他方法的质量如何，情况可能会更糟）。平衡树应该在添加/删除/搜索时获得O(log n)的时间复杂度。 - Alexei Levenkov

@QasimAhmed 这段代码能用吗？ - Saeid

@sudomakeinstall2 请检查一下，现在代码可以运行了。 - Qasim Ahmed

在我看来，它们都等同于O(n)，因为我们有if和for语句。因此，必须遍历每个项，正如大O符号所假定的最坏情况估计一样。 - StepUp

@QasimAhmed 当然会。 - Saeid

Answer 1

让我们来看看Search方法中有什么。它不是二叉树，而且我们使用了递归。因此，Search方法将调用N次，直到我们找到必要的值。所以我们可以得出结论，最多（最坏情况下）需要迭代N次才能在最后一次迭代中找到一个值，因此时间复杂度为O(N)：

public Node search(Node root, int data)
{
    if (root == null)
        return null;

    if (data == root.Value)
        return root;

    Node t = search(root.Children, data);
    if (t == null)
        t = search(root.Sibilings, data);
    return t;
} 

< p>对于加法方法来说，它更简单，因为我们有< code>for语句而且没有嵌套循环。所以我们对于Addition方法的时间复杂度是O(N)。

正如威斯康星大学所说：

因此，对于循环 for (i = 0; i < N; i++) { 一系列语句 } 循环执行了N次，因此语句序列也执行了N次。由于我们假设这些语句是O(1)，所以for循环的总时间是N * O(1)， 总体上是O(N)。

- StepUp