◼︎ 1-2 계산 복잡도
O(n)입니다. 곱셈 n번, 덧셈 n번으로 사칙연산이 총 2n번 필요하지만, O(n)으로 표현합니다.
◼︎ 1-3 계산 복잡도(공식 이용)
O(1)입니다. 덧셈 두 번, 곱셈 세 번, 나눗셈 한 번으로 사칙연산이 총 여섯 번 필요하지만, 이 값은 n의 크기와 상관없이 일정한 값이므로 O(1)로 표현합니다.
◉ 예제 소스 e01-3-sumsq.py
# 연속한 숫자의 제곱의 합을 구하는 알고리즘
# 입력: n
# 출력: 1부터 n까지 연속한 숫자의 제곱을 더한 값
def sum_sq(n):
return n * (n + 1) * (2 * n + 1) // 6
print(sum_sq(10)) # 1부터 10까지 제곱의 합(입력: 10, 출력: 385)
print(sum_sq(100)) # 1부터 100까지 제곱의 합(입력: 100, 출력: 338350)
◉ 실행 결과
385
338350