Какова временная сложность этого алгоритма простых факторов - PullRequest
Новая
       4

Какова временная сложность этого алгоритма простых факторов

0 голосов
/ 27 февраля 2019

Какова будет сложность этой программы для поиска простых множителей числа.И как можно улучшить его (учитывая только временную сложность, а не стандарты кодирования или пространственную сложность).

Спасибо и привет.

См. Исходный код: 

function primes(n) {
  let primeNumbers = [2];

  if (n < 2) {
    return [];
  } else if (n == 2) {
    return [2];
  }

  for (let i = 3; i <= n; i++) {
    let x = i;
    let j = 0;
    let isPrime = true;
    while (j < primeNumbers.length && primeNumbers[j] <= Math.sqrt(i)) {
      if (x % primeNumbers[j] == 0) {
        isPrime = false;
        break;
      } else {
        j++;
      }
    }
    if (isPrime) {
      primeNumbers.push(x);
    } else {}
  }

  return primeNumbers;
}

function primeFactors(n) {
  let primeNumbers = primes(Math.sqrt(n));
  let i = 0;
  let x = n;

  if (n == 1) {
    return [1];
  }

  if (n == 2) {
    return [2];
  }

  let primeFactors = [];

  while (i < primeNumbers.length) {
  
    while (x % primeNumbers[i] == 0) {
      primeFactors.push(primeNumbers[i])
      x = x / primeNumbers[i];
      if (x == 1) {
        break;
      }
    }
    
    if (x == 1) {
      break;
    }
    
    i++;
  }

  if (x == 1) {} else if (x > 2) {
    primeFactors.push(x);
  }

  return primeFactors;
}

console.log("test : " + primes(122));

1 Ответ

0 голосов
/ 01 марта 2019

Это небольшое улучшение в Сите Эратосфена, где вы завершаете алгоритм на шаге i = sqrt (n).Предполагая, что каждый шаг занимает постоянное время, время выполнения равно O (sqrt (n)).

Лучшим алгоритмом является рандомизированный алгоритм простоты, который принимает O (log n).http://www.cs.ust.hk/mjg_lib/Classes/COMP3711H_Fall14/lectures/Randomized_Primality_Handout.pdf

...