시간 복잡도 Time Complexity with Java

시간복잡도란?

 

시간복잡도 :  입력 크기와 알고리즘간의 관계

• 알고리즘의 복잡도를 나타내는 지표 중 하나
• 입력 크기에 대해 프로그램의 동작시간을 가늠해볼 수 있는 수단

// 문자열의 알파벳 구성을 파악하는 코드의 시간 복잡도?
// 주어진 문자열을 한글자씩 순회하면서 각 알파벳에 카운트를 증가시켜주는 코드
// 이 코드의 시간복잡도 : 연산이 얼마나 수행되는지 나타내는 형태
for (int i = 0; i < str.length(); i++) {
	int alphabetIndex = str.charAt(i) - 'A';
    count[alphabetIndex]++;
}

• Big-O / Big-Omega / Big-Theta 와 같은 표기법으로 나타낼 수 있다.
  • 강의에서 다루는 것은 Big-O
  • 정의된 입력 데이터 중 가장 최악의 상황을 포함한 시간의 상한선

 

위의 해당 코드에서 연산이 몇번이나 반복될까?

int i = 0;    --> +1

반복문이 시작할때 i를 초기화 하는 과정 필요, 반복문이 시작할때 처음 한번만 동작 +1

i < str.length();  --> L + 1

반복할지 안할지 결정하는 조건문, 반복문의 처음부터 끝까지 매번 실행됨,
반복문이 끝날때에도 해당 반복문이 false가 나오고 종료되기 때문에 str.length()보다 한번 더 동작하게 된다
str.length()를 L이라는 변수로 표현하면 조건구문에 실행횟수는 L + 1

i++  -->  L

반복문을 무사히 한번 맞칠때 마다 동작하는 부분
i와 str.length()를 비교했을때 true가 나오는 횟수 즉, 반복문의 반복 횟수만큼 적용이 된다 L

  int alphabetIndex = str.charAt(i) - 'A';    --> 2 * L
  count[alphabetIndex]++;

해당 2줄은 1개의 연산으로 본다.
물론 실제로 필요한 연산이 1번이라는 의미는 아니다.
캐릭터에서 'A'를 빼는 연산과, alphabetIndex에 그 값을 할당하는 연산으로 나눠진다
이런 빼기와 할당연산은 기계어로 번역되는 형태가 다를테고, 수행동작도 차이가 있을 것이다
하지만 그런거 까지 따질 수 없기 때문에, 한 라인, 한구문으로 되어있으면 하나의 연산이라고 생각한다.
해당 부분은 반복문이 반복되는 만큼 실행된다 2 * L 만큼

반복문에서 + (1 + L + 1 + L )
반복문 내부에서 + (2 * L)
다 더하면 4 * L + 2

그래서 시간복잡도는 입력된 문자열의 길에 4배만큼 비례한다.
문자열의 길이가 길어질 수록 연산량이 늘어난다.

O(4 * L + 2)

 이 표현을 대문자 O안에 사용함으로써 복잡도를 나타낼건데, 모든 항을 표현하면 길어지기도 하고
 입력 크기와 비례관계를 확인하고 싶은거기 때문에 상수항 2는 생략해준다
 이런 상수항과 같이 1로 나타날수있는 복잡도는 입력과 무관하게 항상 일정한 시간이 걸리는 알고리즘.
 상수복잡도 O(1) 이라고 한다( 덧셈이나 뺄셈부터 기본 문법의 진행 )

비례항 앞에 있는 4 상수도 떼주면 이 코드이 시간복잡도는 O(L)이라고 할 수 있다.

입력된 문자열 길이에 비례한다: O(L)
// 대부분의 알고리즘은 반복문을 기반으로 하게 되는데, 데이터 크기를 N이라고 하면 O(N)

// 알고리즘이 입력 크기에 비례해 선형적으로 증가한다는 의미

선형탐색 O(N) : 반복문을 기반으로 배열의 모든 원소를 순차 탐색하는 형태

 

그렇다면 선형탐색 안에서 또 다른 탐색이 진행되면 어떨까?

 

반복문 안에 반복문이 존재하는 상황

이중 반복문의 시간 복잡도는?

// 입력받은 N개의 배열 a와 M개의 원소를 가진 배열b에 대해
// 모든 쌍에 대해 그 쌍의 곱을 모두 sum에 더해주는 코드이다

long sum = 0;
for (int i = 0; i < N; i++)    <--
	for (int j = 0; j < M; j++)  <--
    	sum += (long)a[i] * b[j];

1번 라인과 같이 상수항에 동작하는 코드를 제외하면,

가장 많이 동작되는 부분은 4번 라인의 sum을 더해나가는 부분

해당 연산은 3번 라인으로인해 M번 반복될거고, 2번라인으로 인해 N번 반복 될 것이다  M x N

전체 시간복잡도는 O(NM)

그렇다고 다중 반복문으로 되어있다고 항상 N의 곱의 형태는 아니다.

 

 

시간 복잡도 분석

코드 부분말고, 전체 프로그램의 복잡도를 계산해보자.

 

2023.08.21 - [알고리즘/백준] - [백준/BOJ][Java][1919] 애너그램 만들기

[백준/BOJ][Java][1919] 애너그램 만들기

public static void main (String[] args) {

	Scanner sc = new Scanner(System.in);
    String a = sc.next();
    String b = sc.next();
    
    int[] countA = getAlphabetCountArray(a);
    int[] countB = getAlphabetCountArray(b);
    
    int ans = 0;
    for (int i = 0; i < 26; i++)
    	ans += Math.abs(countA[i] - countB[i]);
    System.out.println(ans);
}

 

문자열 2개를 입력받아서, 각 a b에 대한 알파벳 카운트를 세어주고, 알파벳 개수의 차이들을 모두 더하면 답이 나오는 문제였다.

이 코드의 시간 복잡도를 보기 위해서는 가장 많이 시간이 소요될 것 같은 함수 호출부분과, 반복문을 보면 된다.

 

반복문의 경우, 

i가 0부터 26까지 가고 있고, Math.abs()함수는 O(1)이기 때문에 O(26), 결국 상수를 다 떼면 O(1)로 상수항이 된다.

 

함수의 경우,

어떻게 동작하는지 알아야 전체 복잡도를 계산할  수 있다.

// 해당 함수의 구현체

public static int[] getAlphabetCountArray(String str) {
	int[] count = new int[26];
    for (int i = 0; i < str.length(); i++) {
    	count[str.charAt(i) - 'a']++;
    return count;
}

string의 길이를 L이라고 하면, 시간복잡도가 O(L)로 나오게 되고,

이 함수 전체의 시간복잡도 역시  O(L)보다 더 큰 다른 연산이 없어서  O(L)이 된다.

 

전체 시간복잡도는 O(L)이다

 

 

시간 복잡도의 필요성

 

코딩테스트에서의 시간 복잡도?

• 현실에서 프로그램의 동작시간은 환경적 요소(서버 스펙 등)에 따라 달라질 수 있다.
  • 코딩테스트 같은 경우에는, 시간복잡도가 출제자가 의도한 풀이 혹은 복잡도 내로 풀이할 수 있는가에 대한 기준이 된다.
• 보편적인 코딩테스트에는 문제마다 시간 제한이 주어진다.
  • 시간 제한이 1초라면, 최악의 테스트케이스에서도 해당 시간 내에 프로그램이 답을 구할 수 있어야 한다.
  • 시간 제한 내에 프로그램이 종료되지 않으면 시간 초과를 받게 된다.
  • 코드를 다 작성하고 제출했더니 시간초과를 받았을때, 더 줄여야겠네보다 내 풀이가 시간제한 내에 동작할 수 있는지 가늠할 수 있다면 시행착오가 훨씬 줄어들 수 있다. 내 풀이가 시간내에 들어갈 것 같지 않다면 다른 풀이를 고안해봐야 한다.
• 편의상 1초에 약 1억 번 연산을 기준으로 소요 시간을 가늠할 수 있다.
  • 상수/ 최적화 등에 따라 시간복잡도가 1천만 밖에 되지않아도 1초를 넘기거나 시간복잡도로 10억이 넘어도 1초안에 실행될 수 있다.
  • 절대적 기준이 아닌 상대적 지표

보다 적합한 알고리즘을 선택할 수 있는 기준

• 올바른 정답을 구하는 알고리즘이 여럿이라면?
  • 시간이 넉넉하다면 구현이 쉬운 방법을 택하거나
  • 제한에 따라 시간/메모리상으로 효율적인 방법을 택할 수 있다.

 

배열의 최댓값을 구하는 함수의 구현

 

1. 반복문을 통해 모든 원소를 비교하는 방법, 시간복잡도 : O(N)

public static int getMaxIntArray(int[] arr) {
	int maxValue = arr[0];
    for (int = 1; i < arr.length; i++0 
    	if (arr[i] > maxValue) maxValue = arr[i];
    return maxValue;
}

반복문을 돌면서 모든 원소를 매번 비교하고 최대값을 갱신한다. 주어진 원소만큼 반복문을 돌게 된다.

 

 

2. 정렬 함수를 이용하는 방법, O(NlogN)? O(N²)?

public static int getMaxInArray(int[] arr) {
	Arrays.sort(arr);
    return arr[arr.length - 1];
}

배열을 오름차순으로 정렬한 뒤, 가장 뒷 원소에 최대값이 있다는 의미이다.

int[]배열에 대한 Arrays.sort함수의 시간복잡도를 보면 된다.

 

• N이 1000만 이라면? - 1번 방법을 써야 한다.
• 둘 중 어느쪽도 상관 없다면? - 편한 방법을 고른다.
  • 2번의 경우 원본배열이 유지되어야 하느냐에 대한 문제도 있지만 부차적인거고, 코드가 훨씬 짧고 편하니까 내 구현효율을 따져서 편한 방법을 고르는게 적합할 수 있다.

 

Java의 시간 제한

 

Java는 왜 추가 시간이 있나요? (BOJ 기준)

https://help.acmicpc.net/judge/time-and-memory

시간과 메모리

• 같은 알고리즘을 구현했어도 언어마다 동작 시간이 다를 수 있다.
• 대부분의 시간/ 메모리 제한은 C/C++ 계열 언어 기준
  • Java의 실행 속도가 C/C++보다 상대적으로 느리다.
• Java는 컴파일 방식으로만 동작하는 언어보다 느린 편
  • Java는 컴파일과 인터프리터 방식이 함께 적용되는 언어이기 때문에, 컴파일언어보다는 느리다.
• 응시 언어가 여러가지인 경우 각 언어의 통과를 보장하기 위해 보정값이 적용될 수 있다.
  • 보장되지 않는 경우도 있다.

 

시간 복잡도를 통한 추론

 

https://en.wikipedia.org/wiki/Time_complexity

Time complexity - Wikipedia

보통은 문제풀이를 세우고 해당 복잡도를 계산했을때 시간제한 안에 들어오는지 계산하지만,

가끔은 입력데이터 범위를 보고 어떤 복잡도가 적용되겠다라고 역추론하기도 한다.

N의 범위	시간 복잡도
N <= 10 ~ 11	O(N!)
N <= 24 ~25	O(2^N)
N <= 300 ~ 500	O(N^3)
N <= 5000 ~ 10,000	O(N^2)
N <= 50,000 ~ 100,000	O(N√N)
N <= 100,000 ~ 1,000,000	O(N log N)
N <=  10,000,000	O(N)
N개의 데이터가 입력이 아닌 범위 등으로 주어질때	O(√N), O(N log N), O(1)

예를 들어, N의 범위가 10정도면 어떤 방법으로 써도 풀리는 문제이기 때문에 모든 방법을 다해보는 팩토리얼복잡도도 괜찮다.

그리고 5000개의 배열을 모든 순서쌍을 조사해야한다면, 굳이 알고리즘을 고려하지 않아도 모든 순서쌍을 2중반복문으로 N^2으로 해도 된다. 하지만 10만이 넘어가게 되면 다른 풀이를 적용해야 한다라고 알 수 있다.

 

문제 풀이에서 보통 log를 사용하게 되면 이때 밑이 없는경우에 이를 log(2) '로그 2에대한 로그'라고 생각해주면 된다.

가끔 N이 어마어마하게 커서, 제시한 입력을 다 받기만해도 시간초과가 나는 경우가 있는데, 데이터를 입력으로 주는게 아니라 범위로 주는게 아니라 프로그램이 생성하게끔 한다. 훨씬 효율적인 알고리즘을 생각해봐야 합니다.

 

---

📕본 포스팅은 패스트캠퍼스의 "핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online." 을 공부하면서 정리한 내용입니다.