4

Вот функция разложения на простые множители:

function primeFactors(n){
    // Print the number of 2s that divide n
    while (n % 2 == 0) {
        console.log(2);
        n = n/2;
    }

    // n must be odd at this point. So we can skip one element
    // (Note i = i +2)
    for (var i = 3; i * i <= n; i = i + 2) {
        // While i divides n, print i and divide n
        while (n % i == 0) {
            console.log(i);
            n = n / i;
        }
    }
    // This condition is to handle the case when n is a prime number
    // greater than 2
    if (n > 2) {
        console.log(n);
    }
}

Автор книги считает, что временная сложность алгоритма равна O(sqrt(N)). Но while цикл, который внутри цикла for имеет сам сложность log n, тоже самое показывает wiki - Перебор делителей. Там написано введите сюда описание изображения. Подскажите, пожалуйста, как всё таки правильно и почему? Книга - JavaScript Data Structures and Algorithms, 3-я глава.

1
  • Вы же сами написали, что там сказано sqrt(n)log(n)
    – tym32167
    12 дек 2019 в 17:00

1 ответ 1

2

Все правы, но по-разному. Это связано с вопросом, а деление 2 чисел друг на друга это 1 операция или нет. Если мы не выходим за пределы размеров машинных слов (64 бита к примеру), то считать деление 1 операцией оправданно, если мы работаем, к примеру, с 2048 бит ключами, то явно нет.

Деление 2 чисел выполняется за log ^2 от них (обычный столбик). Есть и более эффективные методы, но речь не о ним.

Но, сам алгоритм имеет сложность не ниже корня. Использовать для чисел больше условных 10^30 его никто не будет (10^9 в секунду, миллион секунд. Это очень долго). При этом, в эффективных вычислениях, это не больше 4 блоков по 9 разрядов, и умножение делается за 16 операций. В целом вполне O(1).

Поэтому лучше считать, что права именно книга.

P.S. цикл while никак на сложность не влияет, т.к. он суммарно (а не на каждой итерации цикла for) вызовется не более log раз.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.