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

📃 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Long n = Long.parseLong(br.readLine());

        bw.write(n*n + "\n" + 2);

        br.close();
        bw.flush();
        bw.close();

    }
}

✏ 풀이 과정

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

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

알기 쉽게 자바코드로 변환하였고 이 알고리즘은 배열 A의 모든 쌍을 곱으로 합산하여 반환하는 알고리즘인것을 확인할 수 있었다.

시간복잡도 분석

• int sum : 
  • 이 코드는 대입 연산으로 상수 시간 복잡도를 가지며 빅오 표기법으로 $O(1)$ 으로 표현한다.
• int n = A.length :
  • 이 대입 연산도 상수 시간 복잡도를 가지며, 빅오 표기법으로 $O(1)$로 표현된다.
• for (int i = 0; i < n; i++) :
  • 이 반복문은 `i`가 0부터 시작하여 `n` 보다 작을때 까지 반복한다. 따라서 이 반복문은 총 `n`번 실행된다.
  • 즉, 선형 시간 복잡도를 가지며 빅오 표기법으로 $O(n)$ 으로 표현할 수 있다.
• for (int j = 0; j < n; j++)
  • 이 반복문도 마찬가지로 `j`가 0부터 시작하여 `n`보다 작을때 까지 반복하는 코드이다.
  • 따라서 총 `n`번 실행되며 실행 횟수는  `n`의 크기만큼 비례하게 된다. 

 

수식 표현

각 연산의 시간 복잡도를 합산하면 다음과 같다.

$$ T(n)=O(1)+O(1)+O(n2)$$ 

으로 표현할 수 있다.

 

빅오 표기법은 상수 항과 낮은 차수의 항은 무시하고 가장 큰 차수의 항만 고려한다. 따라서 $O(n^2)$ 이 남는다. 즉 이코드의 시간복잡도는 $O(n^2)$이다.