Сложность времени для двоичного представления перестановки из n битов - PullRequest
Новая
       13

Сложность времени для двоичного представления перестановки из n битов

0 голосов
/ 06 января 2019

Я возвращаю приведенный ниже код в java, чтобы получить возможное двоичное представление n цифр. 

public List<String> binaryRepresenation(int n){
    List<String> list = new ArrayList<>();
    if(n>0){
        permuation(n, list, "");
    }
    return list;
}

private void permuation(int n, List<String> list, String str){
    if(n==0){
        list.add(str);
    }else{
        permuation(n-1, list, str+"0");
        permuation(n-1, list, str+"1");
    }
}

Для n = 3 он производит комбинации 001 001 010 011 100 101 110 111. Всего эта функция создает 2 ^ n возможных представлений.

Можно ли сказать, что сложность времени равна n * 2 ^ n

Где 2 ^ n раз метод вызывается для базовых случаев. Чтобы достичь каждого базового случая, он вызвал бы метод перестановки максимум для n раз.

Итак, общая сложность времени верхней границы равна n * 2 ^ n? Пожалуйста, поправьте меня, если я ошибаюсь. Я пришел к такому выводу, основываясь на сложности времени перестановки строк, обсуждаемой в этой теме Сложность времени перестановок строки . Ваша помощь будет высоко ценится.

Ответы [ 2 ]

0 голосов
/ 06 января 2019

Есть небольшая проблема с вашим анализом. Как вы заметили, для каждого базового случая вы должны вызывать функцию n раз. Но некоторые из этих вызовов являются общими для других базовых случаев. Другими словами, вы считаете один и тот же вызов несколько раз.

Это означает, что хотя сложность определенно не может быть больше, чем n * 2 ^ n, на самом деле она может быть ниже.

Чтобы лучше оценить сложность, вы можете посчитать фактическое количество вызовов функции permutation. Один из способов сделать это - рассмотреть возможные значения переменной str.

str будет двоичной строкой длиной, меньшей или равной n. Кроме того, каждый вызов функции permutation получает уникальное значение str. Это означает, что количество вызовов функции равно числу двоичных строк длины <= n. </p>

Сколько таких строк? 1 + 2 + 4 + ... + 2 ^ n = 2 ^ (n + 1) - 1

Итак, количество раз, которое вызывается permutation, равно O(2^n). Но каждый вызов включает в себя операции str + "0" и str + "1". Эти операции занимают O(n) время. Таким образом, чистая временная сложность операции: O(n * 2^n), но по несколько иным причинам, чем вы изначально думали.

0 голосов
/ 06 января 2019

Сложность времени O (2 n ). Каждый вызов функции помещает два новых вызова функции в стек, пока не будет достигнут базовый случай. Визуализируйте дерево для n = 3 следующим образом: 

            ________""________
           /                  \
       ___0___              ___1___
      /       \            /       \
    _00_     _01_        _10_     _11_
   /    \   /    \      /    \   /    \
  000  001 010   011   100  101 110   111

Это идеальное бинарное дерево с 15 узлами и 8 листьями. 2 n + 1 состояний посещаются, но мы можем удалить константу и упростить до O (2 n ).

Конкатенация строк добавляет к сложности множитель n, но использование StringBuilder или контейнера с постоянными операциями push / pop или add / remove должно устранить это, предполагая, что это только деталь реализации, специфичная для вашего размещен код, а не сложность алгоритма в целом.

...