факториальный трейлинг обнуляет проблемы BigO - PullRequest
Новая
       5

факториальный трейлинг обнуляет проблемы BigO

0 голосов
/ 28 мая 2018

когда я отправляю в leetcode, он запускает case 500/502, но не работает, причина: 1808548329. Но когда я запускаю его на своем собственном Mac, он дает тот же ответ, что и принятый.

мой код: 

int trailingZeroes(int n) {
    int count = 0;
    int tmp = 0; //check every number in [1, i]
    for (int i = 1; i <= n; i++) {
        tmp = i;
        while (tmp % 5 == 0) {
            count++;
            tmp /= 5;
        }
    }
    return count;
}

и ответ переменного тока: 

int trailingZeroes2(int n) {
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}

они запускают тот же результат, на моем Mac: 

std::cout << trailingZeroes(1808548329) << std::endl; //452137076
std::cout << trailingZeroes2(1808548329) << std::endl; //452137076

Это причина того, что первое решение непринят из-за time complexity? (потому что я запускаю его на своем Mac, но он дает тот же ответ, что и AC)

как я могу вычислить временную сложность первого решения,

это O(NlogN)?Я не уверен.Вы можете сделать мне одолжение -: -)

отредактировано, удалить фото.

1 Ответ

0 голосов
/ 28 мая 2018

Ваше решение: O(n).

  • Внутренний цикл повторяется не реже одного раза каждые 5 элементов
  • Внутренний цикл повторяется не реже двух раз каждые 25 элементов
  • ...
  • Внутренний цикл повторяется, по крайней мере, k раз каждые 5 ^ k элементов.

Суммируя это, вы получаете, что внутренний цикл выполняется: 

n/5 + n/25 + n/125 + ... + 1 = 
n (1/5 + 1/25 + 1/125 + ... + 1/n)

Это сумма геометрических рядов , которая находится в O(n)

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

Альтернативное решение, однако, работает в O(logn), что значительно более эффективно.

...