Что такое сложность вставки и поиска N-арного дерева?

Question

Я реализую дерево N-1ry в C#. Мне интересно, как я могу рассчитать сложность ниже методов. Вот мой код:

Состав:

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

Какова большая сложность этих методов?

Answer 1

Давайте посмотрим, что у нас есть в Search метод. Это не двоичное дерево, и у нас есть рекурсия. Поэтому метод 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; 
} 

Для метода сложения проще, так как мы имеем for заявление и нет вложенные петли. Итак, у нас есть O(N) для метода Addition.

As Wisconsin university says:

Так что для петель для (I = 0; я < Н; я ++) { последовательность операторов} Цикл выполняется N раз, так что последовательность операторов также выполняет N раз. Поскольку мы принимаем операторы , это O (1), общее время для цикла for равно N * O (1), , который является O (N) в целом.