배열의 시간 복잡도

Point

• 데이터에 자주 접근하거나 읽어야 하는 경우, 배열을 사용하면 좋은 성능을 낼 수 있다.
• 하지만 배열은 메모리 공간을 충분히 확보해야 하기 때문에
  • 할당할 수 있는 메모리의 크기를 확인하고, 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있다.
  • 중간에 데이터 삽입이 많은지 확인해야 한다. 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 시간초과가 발생할 수 있다는 점이다.
• 또한, 원본 배열을 그대로 수정하지 않길 원한다면, clone()메서드를 사용하여 배열을 복사해서 사용하자.

 

sort() 메서드 사용할 경우와 O(N²) 알고리즘 사용할 경우

• 버블정렬은 1초가 걸리지만, sort() 메서드는 0.1초도 걸리지 않는다. 시간 차이가 상당하다.

API 스트림 활용하기

• 반복문을 통해 일일히 데이터를 확인해서 중복값을 확인하고 제거하는 알고리즘은 시간 복잡도가 O(N²)으로 좋지 않으니, 표준 API를 사용하여 유용한 것들을 사용하자.

 

시간 복잡도 N의 가용 범위

시간 복잡도	N의 가용 범위
O(N!)	10
O(2ⁿ)	20~25
O(N의 3제곱)	200~300
O(N²)	3,000~5,000
O(NlogN)	100만
O(N)	1,000~2,000만
O(logN)	10억

가용 가능한 N의 범위가 작다 = 해당 시간 복잡도는 느리다
가용 가능한 N의 범위가 크다 = 해당 시간 복잡도는 빠르다

성능 나쁜 알고리즘: O(N²), O(2ⁿ), O(N!) → 작은 N 아니면 시간 초과
성능 좋은 알고리즘: O(N), O(N log N), O(log N) → 큰 N도 문제 없음

알고리즘 구조	시간복잡도	설명
단일 for문	O(N)	선형 탐색
중첩 for문	O(N²)	완전 탐색
정렬	O(N log N)	Arrays.sort()
정렬 + 탐색	O(N log N)	이진 탐색
이진 탐색 N번	O(N log N)	반복적으로 log N 탐색 수행

- 모든 알고리즘 문제에서 N은 입력 크기, 배열의 길이, 숫자의 개수를 의미한다.
- ex) 정수 배열의 길이가 2이상 10의 5제곱 이하일 때, 제한시간이 3초라면 O(N²) 알고리즘은 사용할 수 없다. why?
N = 배열의 길이 = 10의 5제곱 = 100,000
여기서 O(N²) 을 사용하게 되면, N² = 100,000 * 100,000 = 10,000,000,000 즉, 약 100억번이다.
컴퓨터가 1초에 약 1억번을 연산 가능하다고 했을 때, 3초면 3억번만 가능하다는 건데.. 여기서 100억번으로 3억번을 초과해버리므로 역부족임을 알 수 있다.

 

 

🎯 예제 1: 정렬 후 탐색

 

int[] arr = new int[N];
Arrays.sort(arr); // 정렬

for (int i = 0; i < N; i++) {
    // 무언가 처리
}

• Arrays.sort(arr) → O(N log N) (TimSort 기반)
• for 반복 → O(N)
• 총 시간 복잡도: O(N log N + N) → O(N log N) (큰 항만 남김)

 

🎯 예제 2: 이진 탐색을 N번 하는 경우

int[] arr = new int[N];
Arrays.sort(arr); // 정렬

for (int i = 0; i < N; i++) {
    int idx = Arrays.binarySearch(arr, target); // log N
}

 

• 이진 탐색이 1번당 O(log N)
• 그걸 N번 함 → O(N log N)