2.2.3 여러 알고리즘을 사용할 때 시간 복잡도 생각해보기
하나의 풀이에 여러 개의 알고리즘을 사용한다면 시간 복잡도는 어떻게 계산될까요? 예를 들어 다음 코드처럼 길이가 N인 배열을 이중 반복문으로 순회하는 것은 O(N2)의 시간 복잡도로 나타낼 수 있습니다.
int[] arr = ... // 길이가 N인 배열
for (int a : arr) {
for (int b : arr) {
System.out.println(a + " + " + b + " = " + (a + b));
}
}
순회와 별개로 다음과 같이 배열을 다시 한 번 순회한다면 추가적으로 O(N)의 시간 복잡도가 발생합니다. 이때 총 시간 복잡도는 O(N2+N)이 될 것입니다.
int[] arr = ... // 길이가 N인 배열
for (int v : arr) {
System.out.println(v);
}
for (int a : arr) {
for (int b : arr) {
System.out.println(a + " + " + b + " = " + (a + b));
}
}