c#–Nary树插入和搜索的复杂性是什么？

我在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();
}


这些方法的复杂性是什么？

解决方法:

让我们看一下Search方法中的内容.它不是二叉树,我们有递归.因此,搜索方法将调用N次,直到找到必要的值.因此我们可以得出结论,我们有O(N),其中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;
}


对于Addition方法更简单,因为我们有语句和没有嵌套循环.所以我们有O(N)加法方法.

As Wisconsin university says:

So for loops for (i = 0; i sequence of statements } The loop executes N times, so the sequence of statements also executes N times. Since we assume the

statements are O(1), the total time for the for loop is N * O(1),

which is O(N) overall.