algorithm - 阶乘尾随零 BigO 问题

Question

当我提交到 leetcode 时，它​​运行案例 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;
}

和 ac 答案:

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

第一个解不被接受的原因是时间复杂度吗？ (因为我在自己的 Mac 上运行它，但它给出的答案与 ac 给出的答案相同)

我如何计算第一个解决方案的时间复杂度，

是 O(NlogN) 吗？我不知道。你能帮我一个忙吗？:-)

---

编辑，删除图片。

Answer 1

您的解决方案是O(n)。

• 内循环至少每 5 个项目重复一次
• 内循环至少每 25 个项目重复两次
• ...
• 内部循环每 5^k 项至少重复 k 次。

将它加在一起得到内部循环运行:

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

这是 sum of geometric series ，这是在 O(n)

此外，如果忽略内部循环，外部循环本身有 O(n) 次迭代，每次成本不变，所以这仍然是 O(n)。

---

不过，替代解决方案在 O(logn) 中运行，效率要高得多。