(python) 1 부터 n 까지의 연속한 숫자의 합 ( 제곱의 합)

1부터 n까지 연속한 숫자의 합을 구하는 알고리즘

1. 시간 복잡도 O(n)

def sum(n):
    s = 0
    for i in range(1 , n+1):
        s += i
    return s

print(sum(10))
print(sum(100))

 

2. 시간 복잡도 O(1) , n(n+1) / 6 공식 이용

def sum(n):
    return n * (n+1) // 2

print(sum(10))
print(sum(100))

 

 

1부터 n까지 연속한 숫자의 제곡의 합

(1) 시간 복잡도 O(n)

def sum(n):
    s = 0
    for i in range(1, n+1):
        s += i ** 2
    return s

print(sum(10))
print(sum(100))

 

(2) 시간 복잡도 O(1) , n(n+1)(2n+1) / 6 공식 이용

def sum(n):
    return (n*(n+1)*(2*n+1))//6

print(sum(10))
print(sum(100))