自用笔记36——时间复杂度

    科技2025-01-06  12

    设计一个算法,算出 n 阶乘有多少个尾随零。

    示例 1:

    输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。 示例 2:

    输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个零. 说明: 你算法的时间复杂度应为 O(log n) 。

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/factorial-zeros-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    int trailingZeroes(int n){ int i=0; while(n) { n=n/5; i=i+n; } return i; }

    处理这道题一开始当猪了,一开始想到了尾数0的产生是2和5相乘,然后一开始设计了一个程序判断乘数中2和5的个数。后来一想乘数中2的个数远远多于5,只要判断因数5的个数就行了。然后我又设计了一个程序判断每一个乘数中因数5的个数,然后我反复失败和超时。最后才发现直接统计n!中5的倍数个数,但是会发现有25会多出一个5,有125会多出两个5.。。所以分别统计5、25、125。。。的倍数个数即可,即i=n/5+n/25+n/125+。。。 也就是循环语句n=n/5; i=i+n;

    时间复杂度: O(1):常数复杂度 丨 无论输入有多大,程序运行都需要相同的时间

    O(n2):二次复杂度 丨 处理时间随着输入大小的增加而越来越快-作为一个多项式函数 1项:1秒 10项:100秒 100项:10000秒

    O(n):线性复杂度 丨 程序运行时间随输入大小成比例增加 1项:1秒 10项:10秒 100项:100秒

    O(logn):对数复杂度 丨 程序运行时间增长缓慢,即使输入的大小增长很大 1项:1秒 10项:2秒 100项:3秒 1000项:4秒 10000件:5秒

    https://blog.csdn.net/ffsiwei/article/details/80424275 概念性东西码一下

    Processed: 0.009, SQL: 8