모두의 알고리즘 - 문제 01. 1부터 n까지의 합 구하기 연습문제

def sum_mul(n):
    sum=0
    for i in range(1, n+1):
        sum=sum+(i**2)  # 거듭제곱은 ^ 기호가 아니라 ** 기호더라
    return sum

print(sum_mul(10))


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

print(sum_mul2(10))

1-1. 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for문으로 만들기

 

  배운걸 응용하기만 하면 됐고 거듭제곱 기호가 C와는 다르게 ' ^ '가 아니라 ' ** '인 것을 알게 되었다.

 

1-2. 연습문제 1-1의 시간복잡도는 O(1)인가 O(n)인가?

  

  O(n). 입력값n과 계산 횟수(거듭제곱 한 번, 덧셈 한 번)가 정비례하여 증가하기 때문에 O(n)이다.

 

1-3. 1부터 n까지의 연속한 숫자의 제곱의 합을 구하는 공식은 n(n+1)(2n+1)/6인데 이 공식은 O(1)인가 O(n)인가?

 

  O(1). 입력값의 크기와 관계 없이 계산횟수가 동일하기 때문이다. 입력값을 정해진 공식에 대입하기만 하면 되기에 계산횟수의 변화가 없다.