java - 如何计算这些方法/算法的计算复杂度？

Question

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

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

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总节点。那变得和O(n)一样好如果ar被认为是O(1) , or 如果树的高度保证是可能的最小值。它也将是 O(n)如果这些方法不必处理 null child ，而不是只处理真正的 child 。

方法void graft(Node u, Tree subTree)

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