递归数置换时间复杂度

问题描述 投票:2回答:1

我想出了一段递归生成数字排列的代码但不确定时间复杂度,有人知道它是什么吗?

 private static void maketree(int i) {
        Node<Integer> head = new Node<Integer>(0);
        ArrayList<Integer> hasLeft = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> permutations = new ArrayList<ArrayList<Integer>>();

        for (int tmp = 1; tmp < i; tmp++) {
            hasLeft.add(tmp);
        }

        for (Integer t = 0; t < hasLeft.size(); t++) {
            head.addChild(hasLeft.get(t));
            ArrayList<Integer> start = new ArrayList<Integer>();
            start.add(0);
            fillTree(head.getChildren().get(t), (ArrayList<Integer>) hasLeft.clone(), start, permutations);
        }
    }

    private static void fillTree(Node<Integer> n, ArrayList<Integer> hasLeft, ArrayList<Integer> start,
            ArrayList<ArrayList<Integer>> permutations) {

        ArrayList<Integer> current = (ArrayList<Integer>) start.clone();
        current.add(n.getData());
        hasLeft.remove(n.getData());
        if (hasLeft.isEmpty()) {
            permutations.add(current);
        }

        for (Integer i = 0; i < hasLeft.size(); i++) {
            n.addChild(hasLeft.get(i));
            fillTree(n.getChildren().get(i), (ArrayList<Integer>) hasLeft.clone(), current, permutations);
        }
    }
java time-complexity
1个回答
-1
投票

而不是使用IntegerNumber,使用String,这将帮助你很多。

你可以使用this from GeeksForGeeks代码。

public class Permutation { 
public static void main(String[] args) 
{ 
    String str = "ABC"; 
    int n = str.length(); 
    Permutation permutation = new Permutation(); 
    permutation.permute(str, 0, n - 1); 
} 

/** 
 * permutation function 
 * @param str string to calculate permutation for 
 * @param l starting index 
 * @param r end index 
 */
private void permute(String str, int l, int r) 
{ 
    if (l == r) 
        System.out.println(str); 
    else { 
        for (int i = l; i <= r; i++) { 
            str = swap(str, l, i); 
            permute(str, l + 1, r); 
            str = swap(str, l, i); 
        } 
    } 
} 

/** 
 * Swap Characters at position 
 * @param a string value 
 * @param i position 1 
 * @param j position 2 
 * @return swapped string 
 */
public String swap(String a, int i, int j) 
{ 
    char temp; 
    char[] charArray = a.toCharArray(); 
    temp = charArray[i]; 
    charArray[i] = charArray[j]; 
    charArray[j] = temp; 
    return String.valueOf(charArray); 
} 
} 

互联网是寻求帮助,接受它,为什么只是复杂的运行?

© www.soinside.com 2019 - 2024. All rights reserved.