我们如何找到阶乘中尾随零的大 O 符号？

Question

我知道如何计算阶乘的大 O 表示法，但我很难将这两种表示法结合起来。这是计算尾随零的代码。

using namespace std;

  // Function to return trailing 
  // 0s in factorial of n
 int findTrailingZeros(int n)
 {
   // Initialize result
    int count = 0;

    // Keep dividing n by powers of 
    // 5 and update count
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;

    return count;
}

// Driver Code
int main()
{
   int n = 100;
   cout << "Count of trailing 0s in " << 100
        << "! is " << findTrailingZeros(n);
   return 0;
}

Answer 1

复杂度为O(log(n))。如果您绘制每个 n:

的迭代次数，很容易看出

n        iterations
------   -----------
< 5      0
< 25     1
< 125    2
< 625    3
< 3125   4

Answer 2

准确来说应该是 O(1 - log5(n)) = O(log5(n)) 其中 n 是要确定其阶乘的数字。

Answer 3

5,5^2,5^3....5^k。终于 5^k<=n（在for循环中给定）所以 k<=log5(n) 所以时间复杂度是 thetha(logn)

我们如何找到阶乘中尾随零的大 O 符号？

How can we find big O notation for trailing zeros in factorial?

c++

algorithm

recursion

big-o

factorial