сложность перестановки строк печати

Question

Вот мой код для печати строковых перестановок. Я изо всех сил пытаюсь рассчитать сложность времени функций. Может кто-нибудь предложить несколько указателей. И если есть более эффективный метод времени?

import java.util.ArrayList; 

public class Permutations { 

    public static void main(String[] args){ 
     ArrayList<String> aList = permutation("ABCC"); 
     for(int i=0; i<aList.size(); i++){ 
      System.out.print(aList.get(i) + " "); 
     } 
    } 

    public static ArrayList<String> permutation(String s) { 
     // The result 
     ArrayList<String> res = new ArrayList<String>(); 
     // If input string's length is 1, return {s} 
     if (s.length() == 1) { 
      res.add(s); 
     } else if (s.length() > 1) { 
      int lastIndex = s.length() - 1; 
      // Find out the last character 
      String last = s.substring(lastIndex); 
      // Rest of the string 
      String rest = s.substring(0, lastIndex); 
      // Perform permutation on the rest string and 
      // merge with the last character 
      res = merge(permutation(rest), last); 
     } 
     return res; 
    } 


    public static ArrayList<String> merge(ArrayList<String> list, String c) { 
     ArrayList<String> res = new ArrayList<String>(); 
     // Loop through all the string in the list 
     for (String s : list) { 
      // For each string, insert the last character to all possible postions 
      // and add them to the new list 
      for (int i = 0; i <= s.length(); ++i) { 
       String ps = new StringBuffer(s).insert(i, c).toString(); 
       res.add(ps); 
      } 
     } 
     return res; 
    } 
} 

Answer 1

Для улучшения скорости, то LinkedList будет быстрее, а также с использованием тех же StringBuffer и StringBuffer#setCharAt(int, char). Что-то вроде этого возможно:

List<String> permutations = new ArrayList<String>(initial size); // initial size to avoid multiple arrays to be created 
if (s.length() == 1) { 
    permutations.add(s); 
} else { 
    StringBuffer sb = new StringBuffer(s); 
    loop { // some kind of loop 
     sb.setCharAt(0, 'a'); // do the next permutation 
     permutations.add(sb.toString()); 
    } 
} 
return permutations; 

Answer 2

Обычный merge() is O (n^2). С повторением кажется, что O (n^3)