Сложность алгоритма комбинации строк (как рекурсивная)

Question

У меня есть метод, подобный следующему:

Как я могу рассчитать Big-O?

О (2 ⁿ ) или О (n ⁿ )

Спасибо.

public static void combination(String str, int r) 
{

    int len = str.length();

    if (len == r) myList.add(str);
    if (len == 1) return;

    String newStr = null;
    for (int i = 0; i < len; i++) {
        newStr = str.substring(0, i) + str.substring(i + 1);
        combination(newStr, r);
    }
}

Answer 1

Вот мой намек.

int n = str.length();

Answer 2

Попробуйте преобразовать алгоритм в уравнение, например, X (n + 1) = Функция (X (n)), и разрешите уравнение.

Если вы не можете, попробуйте в начальном случаеX (1) = функция (X (0)), затем X (2) = функция (X (1)) и т. Д. ... Вы заметите закономерность (и, возможно, ответ - это нечто иное, чем O (2 ^)n) или O (n ^ n)).

Просто намеки !!!

Answer 3

(так как это домашнее задание, только подсказки!)

Вы уже выяснили, что делает код? Сколько продукции он производит для данного входа?

Это должно быть нижней границей времени работы алгоритма, так как вы не можете запустить быстрее, чем количество выходов, которое вы должны сгенерировать. Возможно, самым простым способом было бы посмотреть на размер списка для различных входных данных и использовать его в качестве основы.

Answer 4

Для не очень сложного сценария я использую счетчик.

public class Combination {

    private static int count;

    public static void main(String[] args) {

        String[] inputs = new String[] {"12345", "1234", "123", "12", "1"};
        for(String input : inputs){
            count = 0;
            System.out.print("output for " + input + " is:");
            combination(input);
            System.out.println("\nCount for input:" + input + " is " + count);  
        }

    }

    private static void combination(String input) {
        combination("", input);
    }

    private static void combination(String prefix, String input) {
        System.out.print(prefix + " ");
        count++;
        int n = input.length();
        for(int i = 0; i < n; i++){
            combination(prefix + input.charAt(i), input.substring(i + 1));
        }
    }
}

Решение действительно O (2 ^ n)