请分析以下Python代码的时间复杂度
代码时间复杂度分析
先拆解这段代码的核心执行逻辑:
- 外层循环遍历
nums数组的所有元素,假设数组总长度为n。 - 对每个元素
i,内层循环从1遍历到int(sqrt(i)) + 1,这个循环的执行次数为O(√i)。 - 内层循环结束后执行
l.copy(),该操作的时间开销由当前l的元素数量决定——l中存储的是i所有小于等于√i的约数,最多有O(√i)个(比如完全平方数i=k²时,约数个数刚好为k),因此copy操作的时间复杂度也是O(√i)。
综合来看,这段代码的整体时间复杂度为O(Σ(√i))(其中i为nums数组中的每个元素)。如果用数组中的最大元素M简化表达,也可写成O(n * √M)。
内容的提问来源于stack exchange,提问作者Vishak
相关产品推荐
相关产品推荐

