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

📃 풀이

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));

        int n = Integer.parseInt(br.readLine());

        bw.write(n + "\n" + 1);

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

    }
}

✏ 풀이 과정

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

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

이 알고리즘은 배열 A를 파라미터로 받아 배열 A의 길이만큼 순회하면서 배열의 모든 요소의 합을 계산하여 반환하는 알고리즘이다.

시간 복잡도 분석

• int sum = 0 :
  • 이 연산은 상수 시간 복잡도를 가지며, 빅오 표기법으로 O(1)로 표현할 수 있다.
• for (int i = 0; i < A.length; i++) {} :
  • 이 반복문은 배열 A의 모든 요소를 순회한다. 배열의 길이를 $n$ 이라고 하였을 때 반복문은 $n$ 번 실행된다.
  • 즉, 시간 복잡도는 $n$의 크기 만큼 비례하며 이를 빅오 표기법으로 O(n)으로 표현할 수 있다. 
• sum += A[i]
  • 이 연산은 배열 A의 i번째 인덱스에 있는 요소를 sum에 더하는 연산입니다. 상수 시간 복잡도를 가진다.

수식 표현

시간 복잡도를 수식으로 표현하면 다음과 같다.

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

빅오 표기법에서는 상수 항을 무시하고 가장 큰 차수의 항만을 고려하므로. 따라서, 위의 수식에서 $O(1)$은 무시되고, 최종적으로

$$T(n) = O(n)$$

로 표현된다.

여기서 $O(n)$의 차수는 n^1이므로 차수는 1이 된다.