Анализ времени для подмножеств размера k - PullRequest
Новая
       6

Анализ времени для подмножеств размера k

0 голосов
/ 01 декабря 2018 
public static List < List < Integer >> combinations(int n, int k) {
    List < List < Integer >> result = new ArrayListof);
    directedCombinations(n, k, 1, new ArrayList < Integer > (), result);
    return result;
}
private static void directedCombinations(int n, int k, int offset,
    291 List < Integer > partialCombination,
    ListcList < Integer >> result) {
    if (partialCombination.size() == k) {
        result.add(new ArrayList < > (partialCombination));
        return;
    }
    // Generate remaining combinations over {offset , ...» n - 1} of size
    // numRemaining.
    final int numRemaining = k - partialCombination.size();
    for (int i = offset; i <= n && numRemaining <= n - i + 1; ++i) {
        partialCombination.add(i);
        directedCombinations(n, k, i + 1, partialCombination, result);
        partialCombination.remove(partialCombination.size() - 1);
    }
}

Какой временной анализ для этого решения, моя книга говорит, что это O (n * nCk)?nCk имеет смысл, но не понимаю, почему это n * nCk.Ценю всю вашу помощь.

1 Ответ

0 голосов
/ 01 декабря 2018

Из-за этой строки: 

result.add(new ArrayList < > (partialCombination));

Вы создали C(n,k) решения.Теперь для каждого из них вы создаете массив.Это занимает время, пропорциональное его размеру, а именно O(k).Поэтому было бы точнее сказать, что время равно O(k * C(n,k)).

Итак, если вам не нужно было выводить массив, а вернуть, скажем, 1 или сумму чисел вмассив, вы можете заставить алгоритм работать в O(C(n,k)).

...