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

📃 제출 코드

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 = Integer.parseInt(br.readLine());
        bw.write(n * n * n + "\n" + "3");

        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++) {
			for (int k = 0; k < n; k++) {
				sum += A[i] * A[j] * A[k];
				}
			}
		}
	return sum;
}

코드를 보았을때 이 알고리즘을 배열의 특정 삼중 쌍의 곱을 합산하여 반환하는 알고리즘인것을 확인할 수 있다.

시간 복잡도 분석

• int sum = 0 :
  • 대입 연산 -> 상수 시간 복잡도
• int n = A.length;
  • 대입 연산 -> 상수 시간 복잡도
• for (int i = 0; i < n; i++) :
  • 이 반복문은 i가 0부터 n 보다 작을 때 까지 반복한다.
  • 선형 시간 복잡도를 가지며 O(n)으로 표현할 수 있다.
• for (int j = 0; j < n; j++):
  • 내부 반복문으로 j가 0부터 n 보다 작을 때 까지 반복한다.
  • 선형 시간 복잡도를 가지며 O(n)으로 표현할 수 있다.
• for (int k = 0; k < n; k++):
  • 내부 반복문으로 k가 0부터 n 보다 작을 때 까지 반복한다.
  • 선형 시간 복잡도를 가지며 O(n)으로 표현할 수 있다.

 

총 시간 복잡도

• 첫 번째 반복문이 n번 실행되고, 내부에 두 번째 반복문이 n번 실행된다.
• 두 번째 반복문 안에 세 번째 반복문이 n번 실행된다.
•  

 

결과적으로

$$T(n) = n * n * n  = n^3$$ 

빅오 표기법에서는 상수 항과 낮은 차수의 항을 무시하고, 가장 큰 차수의 항만을 고려한다.

따라서 최종적으로 $O(n^3)$ 이 된다.