33 lines
737 B
Python
33 lines
737 B
Python
|
"""
|
||
|
|
性能对比：循环累加 vs 高斯求和公式
|
||
|
|
比较两种算法计算 1+2+...+n 的耗时差异
|
||
|
|
"""
|
||
|
|
import time
|
||
|
|
|
||
|
|
def sum_by_loop(n):
|
||
|
|
"""循环累加 O(n)"""
|
||
|
|
total = 0
|
||
|
|
for i in range(1, n + 1):
|
||
|
|
total += i
|
||
|
|
return total
|
||
|
|
|
||
|
|
def sum_by_gauss(n):
|
||
|
|
"""高斯求和公式 O(1)"""
|
||
|
|
return n * (n + 1) // 2
|
||
|
|
|
||
|
|
# 测试不同规模
|
||
|
|
for n in [1000, 10000, 100000, 1000000]:
|
||
|
|
print(f"\n--- n = {n} ---")
|
||
|
|
|
||
|
|
start = time.time()
|
||
|
|
r1 = sum_by_loop(n)
|
||
|
|
t1 = time.time() - start
|
||
|
|
|
||
|
|
start = time.time()
|
||
|
|
r2 = sum_by_gauss(n)
|
||
|
|
t2 = time.time() - start
|
||
|
|
|
||
|
|
print(f"循环累加: {t1:.6f} 秒, 结果 = {r1}")
|
||
|
|
print(f"高斯公式: {t2:.6f} 秒, 结果 = {r2}")
|
||
|
|
print(f"加速比: {t1/t2:.2f}x")
|