阶乘尾随零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;
}

交流答案是：

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项至少重复两次
• 内部循环每5k个项目至少重复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）中运行，效率显著提高。