[백준 | 시간복잡도] 알고리즘 수업 - 알고리즘의 수행 시간 4

📃 제출 코드

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n= sc.nextInt();
        System.out.println((n*(n-1))/2);
        System.out.println(2);
    }
}

✏ 풀이 과정

먼저 문제에서 주어진 의사코드를 자바 코드로 변환하였다.

MenOfPassion(A[]) {
	int sum = 0;
	int n = A.length; 
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			sum += A[i] * A[j]; 
		}
	}
	return sum;
}

이 알고리즘은 배열 A를 입력으로 받아 배열의 특정 쌍의 곱을 합산하여 반환하는 알고리즘이다.

시간 복잡도 분석

• int sum :
  • 대입 연산으로 상수 시간 복잡도를 가진다.
• int n = A.length :
  • 마찬가지로 상수 시간 복잡도를 가진다.
• for (int i = 0; i < n -1; i++) :
  • 이 반복문은 i가 0부터 시작하여 n - 1 보다 작을때 까지 반복한다. 따라서 n - 1 번 반복한다.
  • 선형 시간 복잡도를 가지며 빅오 표기법으로 $O(n-1)$으로 표현할 수 있다. 하지만 상수항은 무시하므로 
  • $O(n)$ 으로 표현한다.
• for (int j = i + 1; j < n; j++) :
  • 이 반복문은 내부 반복문으로 반복 횟수가 `i` 에 따라 달라지며 각 `i`에 대해 반복문 `j`는 $ n - i - 1$ 번 실행된다.

총 실행 횟수

• 외부 반복문이 `i` 에 대해 n-1번 반복되고, 내부 반복문은 각 i에 대해 `n - i - 1`번 실행된다.
• 전체 실행 횟수는 두 반복문이 결합된 횟수를 계산한 것이다.

총 실행 횟수 $T(n)$ 은 다음과 같이 계산할 수 있다.

이를 전개하면

이는 등차수열의 합과 같으며, 총 실행 횟수는 다음과 같다.

위 수식을 단순화하면 $\frac{(n^2-n)}{2}$ 으로 표현할 수 있으며 빅오 표기법에서 상수와 낮은 차수 항을 무시하고 가장 큰 차수의 항만고려하므로 $T(n) = O(n^2)$ 으로 표현할 수 있다.