[BOJ / Python] 24265 알고리즘 수업 - 알고리즘의 수행 시간4

문제

백준 24265 알고리즘 수업 - 알고리즘의 수행 시간4

코드

#BOJ 24265 알고리즘 수업 - 알고리즘의 수행 시간4

n = int(input())
print(int((n-1)*n/2))
print(2)

코드 설명
코드 1, sum <- sum + A[i] x A[j]이 두 개의 for문 안에 들어있다.
첫 번째 for문은 1부터 n-1까지, 두 번째 for문은 i+1부터 n까지 반복한다.

i=1일 때 j가 (n-1)번 반복
i=2일 때 j가 (n-2)번 반복
i=3일 때 j가 (n-3)번 반복
...
i=n-1일 때 j가 1번 반복

$\small \displaystyle\sum_{k=1}^{n-1}{k}=\frac{(n-1) \times n}2$

따라서 코드 1의 수행횟수는 (n-1)*n/2 번이고, 최고차항의 차수는 2이다.