Какова временная сложность этой функции C ++? - PullRequest
Новая
       5

Какова временная сложность этой функции C ++?

0 голосов
/ 18 апреля 2011

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

bool PrimeFactor(int n){
    int count = 0;// count divisors

    for (int i = 2 ; i < n; i++){
        if ( n % i == 0 ){
            if ( PrimeFactor(i)){              
                cout << i << endl;
            }
            count ++;
        }
    }

    if (count > 0)//not prime
        return false;
    return true;
}

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

Ответы [ 3 ]

3 голосов
/ 21 апреля 2011

Это в основном более расширенная версия ответа Бена Фойгта.

Как сказал Бен Фойгт, версия без условия - O(n), это должно быть просто.

Теперьверсия с условной версией выполнит рекурсию внутри оператора if количество раз, равное количеству делителей n (= значение функции делителей для n = d(n)).

Нижний предел inf d(n) = 2, поскольку для каждого простого числа это будет верно, и существует бесконечно много простых чисел, поэтому независимо от того, насколько вы велики n, вы всегда можете найти такое, для которого d(n) = 2.Это означает, что для простых чисел ваша функция будет повторяться 0 раз и имеет сложность O(n).

Верхний предел более сложный (и мне нужен кофе), поэтому давайте пропустим это на мгновение и посчитаем среднеесложность.Средняя сложность d(n) = O(log n), поэтому, как заявил Бен Фойгт, исходная функция будет иметь среднюю сложность O(n log n loglog n ...).Более подробно: у вас есть цикл for, равный O(n), в этом цикле for вы будете возвращать в среднем d(n) = O(log n) раз.Теперь вы снова входите в функцию и повторяете O(log (log n)) раза и т. Д. И т. П.

Также обратите внимание на комментарии к вашему вопросу от DarkDust & Jeff Forster.Он не будет работать так, как вы этого хотите.Кроме того, проверка, разделяют ли четные числа n, бесполезна, поскольку четные числа никогда не будут простыми числами (за исключением, конечно, 2).Из-за рекурсии вы будете вводить внутренний if (тот, у которого cout) во время рекурсивных вызовов, поэтому полученный вами результат не будет тем, что вы хотите (я предполагаю, что это различные простые делители n).

Еще один способ сэкономить время - это тестирование только до floor(sqrt(n)).Если число i делит n точно, проверьте, является ли частное j = n / i также простым числом.Например, для n = 6 вы можете проверить до floor(sqrt(6)) = 2.Затем вы обнаруживаете, что i = 2 является делителем, и вы проверяете j = 6 / 2 = 3.В этом случае вы обнаружите, что i и j являются простыми делителями.

2 голосов
/ 18 апреля 2011

Это упрощение будет повторяться не реже, чем оригинал, и имеет сложность O(n!). Так что это верхняя граница. 

bool PrimeFactor(int n)
{
    for (int i = 2 ; i < n; i++) PrimeFactor(i);
}

Я думаю, что сложность оригинала составляет O(n log n loglog n ...).

0 голосов
/ 21 марта 2014

Я попытался перевести (в рекуррентное отношение) и решить ваш алгоритм формальным образом, как показано ниже:

enter image description here

Порядок роста неполином , что является алгоритмом, которого следует избегать!

...