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

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

풀이 코드 및 설명

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

• 문제 알고리즘

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

위 알고리즘의 시간 복잡도를 구하는 문제이다.

외부 for 문은 i = 1 부터 n-1 까지 반복한다.
내부 for 문은 j = i + 1 부터 n 까지 반복한다.

문제 예제 입력에 있는 7을 n이라고 했을 때

i = 1 일때 j 는 2 ~ 7
i = 2일 때 j 는 3 ~ 7
...
i = 7 일 때 j 는 8이 되어 반복하지 않는다.

n 을 n-1 번 더한 수에서 첫째항이 1 ~ 마지막 항이 n - 1 등차 수열의 합을 뺴면 된다.
따라서 O(n) = n(n-1) - (n-1)n/2)
최고 차항은 항상 2 가 된다.