问题描述:

I am implementing an N-1ry tree in C#. I am wondering how can I calculate the complexity of below methods. Here is my code:

Structure:

public class Node

{

public int Value { get; set; }

public Node Children { get; set; }

public Node Sibilings { get; set; }

}

This method for searching:

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;

}

This method for insertion:

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;

}

}

}

Program entry point:

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

}

What is the bigO complexity of these methods?

网友答案:

Let's see what we have in Search method. It is not a binary tree and we have recursion. So the Search method will call N times till we find a necessary value. So we can conclude that we have O(N) where N is the maximum(worst) number of iteration to find a value at the last iteration:

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

For Addition method is simpler as we have for statement and no nested loops. So we have O(N) for Addition method.

As Wisconsin university says:

So for loops for (i = 0; i < N; 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.

相关阅读:
Top