Алгоритм найти факторику для заданного числа n, которое работает во время O (log n) - PullRequest
Новая
       22

Алгоритм найти факторику для заданного числа n, которое работает во время O (log n)

0 голосов
/ 28 ноября 2018

Я только что написал код, который выполняет свою работу, но я должен оптимизировать его, чтобы он работал вовремя O(log n).Проблема в том, что я не уверен, хороша ли его временная сложность, и если нет, то как мне это исправить?

Фактородическое представление числа представляет собой последовательность s k , s k-1 ... s 2 , s 1 , что:

Мой код: 

unsigned long long int n;
unsigned long long int maxFact[21] = {0};

maxFact[0] = 1;
maxFact[1] = 1;

cout<<"Insert n: "; cin >> n;

int i = 2;
while (maxFact[i-1] * i <= n)  // find higher factorial <= n
{
    maxFact[i] = maxFact[i-1] * i;
    i++;
}

cout << "Factoradic representation of " << n << ":" << endl;

while (i > 1)
{
    cout << n / maxFact[i-1] << " ";
    n = n % maxFact[i-1];
    i--;
}

1 Ответ

0 голосов
/ 28 ноября 2018

Основываясь на примере, используемом в этом факторном определении , вы можете использовать div() для более быстрого определения коэффициентов.Вы можете реализовать это как 

div_t result;
while (n != 0) {
  result = div(n, i);
  n = result.quot;
  maxFact[i++] = result.rem;
}

Где div() и div_t включены из stdlib.h.

Это довольно похоже на то, что у вас есть, за исключением того, что maxFact теперь явно хранит коэффициенты и требует только один цикл для вычислений.Ваш код выглядит так, как будто он, по крайней мере, близок к O (log n), но, выполняя это, как показано выше, уменьшает количество флопов / n, в то же время алгоритмически O (log n) - немного более эффективно, но не превосходно по алгоритму.На самом деле код в этом ответе выполняется в среднем в 3 раза быстрее, чем код в вопросе, для n больше 10 - но здесь мы делим микросекунды (даже до предела точности n), поэтому коэффициент 3 равенпрактически бессмысленно.

Надеюсь, это поможет

...