第30186题 单选题
计算从1到n（n为正整数）的所有正整数之和，以下哪种实现方案是经过数学推导优化后的时间复杂度最优的方案？

假设n的取值范围为1 ≤ n ≤ 10^9，忽略整数溢出问题。

A

从1到n逐个遍历累加求和，时间复杂度O(n)

B

递归实现f(n) = f(n-1) + n，边界条件f(1)=1，时间复杂度O(n)

C

使用高斯求和公式sum = n*(n+1)/2直接计算，时间复杂度O(1)

D

预先生成前缀和数组，查询时直接取对应下标值，查询时间复杂度O(1)

程序运行统计
暂无判题统计
知识点：
算法基础-简单数学推导优化
提交0次 正确率0.00%
答案解析
上一题 下一题