Временная сложность генерирующей функции powerset - PullRequest
Новая
       23

Временная сложность генерирующей функции powerset

2 голосов
/ 08 января 2011

Я пытаюсь выяснить временную сложность функции, которую я написал (она генерирует набор мощности для данной строки): 

public static HashSet<string> GeneratePowerSet(string input)
{
    HashSet<string> powerSet = new HashSet<string>();

    if (string.IsNullOrEmpty(input))
        return powerSet;

    int powSetSize = (int)Math.Pow(2.0, (double)input.Length);

    // Start at 1 to skip the empty string case
    for (int i = 1; i < powSetSize; i++)
    {
        string str = Convert.ToString(i, 2);
        string pset = str;
        for (int k = str.Length; k < input.Length; k++)
        {
            pset = "0" + pset;
        }

        string set = string.Empty;
        for (int j = 0; j < pset.Length; j++)
        {
            if (pset[j] == '1')
            {
                set = string.Concat(set, input[j].ToString());
            }
        }
        powerSet.Add(set);
    }
    return powerSet;
}

Итак, моя попыткаthis:

  • пусть размер входной строки будет n
  • во внешнем цикле for, должен повторяться 2 ^ n раз (потому что установленный размер равен 2 ^ n).
  • во внутреннем цикле for, мы должны выполнить итерацию 2 * n раз (в худшем случае).

1.Таким образом, Big-O будет O ((2 ^ n) * n) (так как мы опускаем константу 2) ... это правильно?

И n * (2 ^ n) хужечем n ^ 2.

, если n = 4, тогда
(4 * (2 ^ 4)) = 64
(4 ^ 2) = 16

, если n = 100затем
(10 * (2 ^ 10)) = 10240
(10 ^ 2) = 100

2.Есть ли более быстрый способ получения мощности или это оптимально?

Ответы [ 2 ]

4 голосов
/ 08 января 2011

Комментарий:

вышеуказанная функция является частью вопроса об интервью, когда программа должна взять строку, а затем распечатать слова в словаре, буквы которых являются поднабором анаграммы входной строки (например, Input: tabrcoz Output: boat, машина, кот и т. д.). Интервьюер утверждает, что реализация n * m тривиальна (где n - длина строки, а m - количество слов в словаре), но я не думаю, что вы можете найти допустимые подстроки данной строки. Кажется, что интервьюер неверен.

Мне дали тот же вопрос на собеседовании, когда я давал интервью в Microsoft в 1995 году. По сути, проблема заключается в реализации простого алгоритма игры в скрэббл.

Ты идешь совсем не в том дереве с этой идеей генерации набора мощности. Хорошая мысль, явно слишком дорогая. Оставь его и найди правильный ответ.

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

1 голос
/ 08 января 2011

2.Есть ли более быстрый способ генерировать набор мощности или это оптимально?

Ваш алгоритм разумен, но ваша обработка строк может использовать улучшения.

string str = Convert.ToString(i, 2);
string pset = str;
for (int k = str.Length; k < input.Length; k++)
{
    pset = "0" + pset;
}

Все, что вы здесь делаете, это настраивает битовое поле, но с использованием строки.Просто пропустите это и используйте переменную i напрямую. 

for (int j = 0; j < input.Length; j++)
{
    if (i & (1 << j))
    {

При создании строки используйте StringBuilder, а не создавайте несколько строк.

// At the beginning of the method
StringBuilder set = new StringBuilder(input.Length);
...
// Inside the loop
set.Clear();
...
set.Append(input[j]);
...
powerSet.Add(set.ToString());

Изменит ли это сложность вашего алгоритма?Нет. Но это значительно уменьшит количество создаваемых вами дополнительных объектов String, что обеспечит вам хорошее ускорение.

...