如何计算这些methods/algorithms的计算复杂度？

Question

我正在 Java 做一个关于 k-ary 树实现的大学项目，现在我需要计算我以前实现的一些方法（或算法）的计算复杂度（最坏情况）。

在每个方法的末尾，我都写了我认为该方法的计算复杂度应该是多少。

int ar; //arity of tree, given by user
List<Node<T>> children = new ArrayList<Node<T>>(ar);

public void addChild(Node<T> n) {
    if(this.numberOfChildren()>=ar){
        System.out.println("Impossible to add: "+n.getInfo());
    }else{
        for(int i = 0; i<ar; i++){
            if(this.children.get(i)==null){
                n.setParent(this);
                this.children.set(i,n);
                break;
            }
        }
    }
}

计算复杂度：O(n)。

public int numberOfChildren() {
    int count = 0;
    for(int i = 0; i<ar; i++){
        if(this.children.get(i)!=null){
            count++;
        }
    }
    return count;
}

计算复杂度：O(n)。

public LinkedList<T> visitDFSA() {
    LinkedList<T> nodiVisita=new LinkedList<T>();
    LinkedList<Node<T>> stack=new LinkedList<Nodo_m_ario<T>>();
    stack.addFirst(this.root);
    while(!stack.isEmpty()){
        Nodo_m_ario<T> u=stack.removeFirst();
        if(u!=null){
            nodiVisita.addLast(u.getInfo());
            for(int i=Node.ar-1;i>=0;i--){
                stack.addFirst((u.childrenList().get(i)));
            }
        }
    }
    return nodiVisita;
}

计算复杂度：O(n²)。

public LinkedList<T> simmetricVisit(Node<T> node) {
    if (node==null){

    }else{
        for (int i=0;i<Node.ar/2;i++){
            simmetricVisit(node.children.get(i));
        }
        vs.add(nodo.getInfo());
        for (int i=Node.ar/2;i<Node.ar;i++){
            simmetricVisit(node.children.get(i));
        }
    }
    return vs;
}

计算复杂度：O(n)。

public void graft(Node<T> u, Tree<T> subTree) {
    if(u==null){
        System.out.println("Can't add the subtree to node u.");
    }else{
        Node<T> rootSubTree = subTree.getRoot();
        rootSubTree.parent = u;
        u.addChild(rootSubTree);
    }
}

计算复杂度：O(1)。

是不是我写的有问题（说的是计算复杂度值）？我认同。所以我想我可能需要一些帮助...:(

Answer 1

方法`void addChild(Node<T> n)`和`int numberOfChildren()`

这些方法中的每一个都执行最多 ar 次单个循环的迭代。假设在这些循环中执行的操作（各种numberOfChildren()、Node.setParent()和Node.getInfo()）是O(1)，这些方法是O(ar)，即O(1) 除非你用 arity 做一些非常奇怪的事情。或者，对于任何给定的 ar 作为常量 ，这些方法肯定是 O(1)，而不管为 ar 选择的实际值。

方法`LinkedList<T> visitDFSA()`和`LinkedList<T> simmetricVisit(Node<T> node)`

这些不太明显，但似乎每个方法只访问每个节点一次，每次访问的成本为 O(ar)。这使得这两种方法 O(n * ar) 总计 n 个节点。如果 ar 被认为是 O(1)、或如果保证树的高度是可能的最小值，那么它变得和 O(n) 一样好。如果这些方法不必处理 null children，而是仅处理真正的 children.

，那么它也将是 O(n)

方法void graft(Node u, Tree subTree)

假设Node.addChild()和Tree.getRoot()各为O(1)，执行固定的最大操作次数。那是 O(1).

如何计算这些methods/algorithms的计算复杂度？

How to calculate computational complexity of these methods/algorithms?

java

algorithm

tree

data-structures

方法`void addChild(Node<T> n)`和`int numberOfChildren()`

方法`LinkedList<T> visitDFSA()`和`LinkedList<T> simmetricVisit(Node<T> node)`

方法void graft(Node u, Tree subTree)

如何计算这些methods/algorithms的计算复杂度？

How to calculate computational complexity of these methods/algorithms?

java

algorithm

tree

data-structures

方法void addChild(Node<T> n)和int numberOfChildren()

方法LinkedList<T> visitDFSA()和LinkedList<T> simmetricVisit(Node<T> node)

方法void graft(Node u, Tree subTree)

方法`void addChild(Node<T> n)`和`int numberOfChildren()`

方法`LinkedList<T> visitDFSA()`和`LinkedList<T> simmetricVisit(Node<T> node)`