모두의 알고리즘 - 문제 01. 1부터 n까지의 합 구하기, 시간 복잡도 개념

def sum_n(n):
    s=0
    for i in range (1, n+1): # 1 이상 n+1 미만
        s=s+i
    return s

print(sum_n(10))
print(sum_n(100))

def sum_n2(n):
    return n*(n+1)//2  # /는 소숫점 나오는 나눗셈, //은 정수 나눗셈

print(sum_n2(10))
print(sum_n2(100))

 

첫 번째 방법은 흔히 프로그래밍을 처음 입문하는 사람들이 배우는 방법인데 이는 숫자가 1 늘어나면 계산 횟수가 1회 늘어나는 방식이다. 즉 1000을 입력하면 1000번 더해야한다.

 

0 + 1 + 2 + 3 + 4 + 5 -> 5를 입력하면 5번 더하게 된다.

 

두 번째 방법은 가우스가 만들었다 알려진 공식을 이용하는 방법이다. 이 공식을 이용하면 1부터 n까지의 합을 쉽게 구할 수 있다. 이 방법은 어떤 값을 입력해도 덧셈 한 번(n+1), 곱셈 한 번(n*(n+1)), 나눗셈 한 번(n*(n+1)//2) 총 3번만 계산하면 값을 얻을 수 있다.

 

시간 복잡도로 표현하자면 첫 번째 방법은 필요한 계산 횟수와 입력 크기가 정비례하므로 'O(n)'으로 표현할 수 있고,

두 번째 방법은 입력 크기와 무관하게 필요한 계산 횟수가 동일하기 때문에 'O(1)'으로 표현할 수 있겠다.