O(n)과 O(log n)의 성능 차이

 

Big O의 O(n)과 O(log n)의 성능 비교
실생활에서 O(n)만큼의 시간이 드는 행위, O(log n)만큼의 시간이 드는 행위를 찾고, 코드로 구현해 실행 결과를 확인한 뒤, 성능 차이를 비교한 문서입니다.

 

---

Big O 표기법

 

Big O에서 O(n)과 O(log n)

O(n)과 O(log n)은 시간 복잡도와 공간 복잡도를 표현하는 점근 표기법(Big O 표기법의) 중 하나이다. 입력 데이터의 크기를 n이라고 할 때, 연산 횟수가 최대 n만큼 필요한 경우를 O(n), log n 만큼 필요한 경우 O(log n) 으로 표현한다.

예를 들어 데이터의 크기가 1백만 개(1_000_000)일 때,
O(n)은 1_000_000 번을, O(log n)은 (*일반적으로 log의 밑은 10이나, Big O 에서 log의 밑은 2) 약 20번의 연산이 필요하다.

 

---

 

실생활 예시

 

(1) 도서관에서 책 찾기

원하는 책을 찾고자 한다.

O(n) : 어질러져 있는 책들 속에서 내가 원하는 책을 찾을 때, 하나하나 일일이 비교하며 찾는다.

 

이 방식은 선형 탐색 (Linear Search)으로, 원하는 책을 가장 뒤에 찾게 되는 경우(최악의 경우)에 n번을 비교해야 하므로, 시간 복잡도가 O(n)에 해당된다.

 

코드 구현 예시 (*책의 순서는 0번으로 시작합니다.)

public class Main {
    public static void main(String[] args) {
        String[] bookCase = new String[5];
        bookCase[0] = "Snow White and the Seven Dwarfs";
        bookCase[1] = "Little Red Riding Hood";
        bookCase[2] = "Hansel and Gretel";
        bookCase[3] = "The Three Little Pigs";
        bookCase[4] = "Cinderella";

        String target = "Cinderella";

        for(int i = 0; i < bookCase.length; i++){
            System.out.println(i + "번째 비교 (찾는 과정, 연산 수행)");
            if(bookCase[i].equals(target)){
                System.out.println(target + " is located at " + i );
            }
        }
    }
}

실행 결과

 

내가 찾는 책이 가장 마지막에 있을 때를 상정하여, 입력 데이터 5개에 5번의 연산 수행이 이루어집니다. 

 

---

 

O(log n) : 사전 순으로 정리되어 있는 책들 속에서 원하는 책을 찾을 때, 탐색 범위를 반씩 줄여가며 찾는다.

 

이 방식은 이진 탐색(Binary Search)으로, 원하는 책을 탐색의 마지막에 찾게 될 경우(최악의 경우) 비교 횟수가 log n번으로 줄어들어, 시간 복잡도는 O(log n)에 해당한다.

 

코드 구현 예시 (*책의 순서는 0번으로 시작합니다.)

import org.w3c.dom.ls.LSOutput;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String[] bookCase = new String[5];
        bookCase[0] = "Snow White and the Seven Dwarfs";
        bookCase[1] = "Little Red Riding Hood";
        bookCase[2] = "Hansel and Gretel";
        bookCase[3] = "The Three Little Pigs";
        bookCase[4] = "Cinderella";
        Arrays.sort(bookCase); // 배열을 정렬해주는 Java 내장 Arrays 클래스의 메서드

        String target = "Cinderella";

        // Arrays 클래스에 이진 탐색 메서드도 존재합니다.
        // int index = Arrays.binarySearch(bookCase, target);

        int num = 0;
        int left = 0;
        int right = bookCase.length - 1;

        while(left <= right){
            System.out.println( num + "번째 비교 (찾는 과정, 연산 수행)");
            int mid = (left + right) / 2;
            // 오버 플로우*를 방지하고 싶을 때, 지금 코드에선 필요없습니다.
            // int mid = left + (right - left) / 2;

            if(bookCase[mid].equals(target)){
                System.out.println(target + " is located at " + mid);
                break;
            }

            // 기준값.compareTo(비교값)는 숫자, 문자열을 비교합니다
            // 기준값이 비교값보다 크면 양수(1) 반환
            // 기준값이 비교값보다 사전적으로 뒤에 있으면 양수(1)를 반환
            // 내가 찾는 책이 중간에 배치된 책보다 앞 쪽이면
            if(target.compareTo(bookCase[mid]) < 0){
                // 앞 쪽에서 탐색
                right = mid - 1;
            }else{
                // 아니라면, 뒤 쪽에서 탐색
                left = mid + 1;
            }

            num++;
        }

    }
}

 

*오버 플로우 간단 설명(내용에서 벗어나는 설명이기에 접은 글 표시해둡니다)

int 자료형은 32비트 자료형입니다. -2,147,483,648 ~ 2,147,483,647 (-2^31 ~ 2^31 -1)의 표현 범위를 가집니다.

주어진 값이 int 자료형이 표현할 수 있는 범위를 넘어버릴 때(ex. 2,147,483,648 과 같이 차이가 1 밖에 나지 않더라도) 오버 플로우(overflow)라고 얘기합니다.

실행 결과

 

내가 찾는 책이 탐색의 마지막에 있을 경우를 상정하여, 입력 데이터 5개에 2번의 연산 수행이 이루어집니다. 

 

 

(2) 비밀번호 알아맞추기

비밀번호 네 자리를 알아내려고 한다.

 

O(n) : 0000 부터 9999까지 하나씩 시도하며 입력해본다. 하나하나 일일이 비교하며 찾는다.

 

코드 구현 예시

public class Main {
    public static void main(String[] args) {
        int num = 0;
        int target = 9999;
        for (int i = 0; i < 10000; i++) {
            num++;
            // 4자리 숫자를 0000부터 9999까지 출력
            System.out.printf("%04d\n", i); // %04d는 4자리로 출력 (앞에 0을 채움)
            if(target == i){
                System.out.println("Password is " + i);
                break;
            }
        }
        System.out.println(num + "번째 비교 (찾는 과정, 연산 수행)");
    }
}

 

실행 결과

 

비밀번호가 9999 였을 때를 상정하여, 입력 데이터 10_000 개에 10_000번의 연산 수행이 이루어집니다.

 

---

 

O(log n) : 0000부터 9999까지 수에서 탐색 범위를 반씩 줄여가며 mid 값을 입력해본다.

 

 

코드 구현 예시

public class Main {
    public static void main(String[] args) {
        int num = 0;
        int target = 9999;

        int left = 0;
        int right = 9999;
        while(left <= right){
            num++;
            int mid = (left+right) /2;

            if(mid == target) {
                System.out.println("Password is " + mid);
                System.out.println(num + "번째 비교 (찾는 과정, 연산 수행)");
                break;
            }
            if( mid < target ){
                left = mid + 1;
            } else {
                right = mid - 1;
            }

        }

    }
}

실행 결과

 

비밀번호가 9999 였을 때를 상정하여, 입력 데이터 10_000 개에 14번의 연산 수행이 이루어집니다.

 

---

실생활 예시로 성능 차이 비교하기

O(n) 은 데이터 크기만큼 연산이 늘어나는 반면, O(log n)은 데이터 크기가 증가해도 연산 횟수가 크게 증가하지 않는다.

도서관에서 책 찾기 예시에서 5만큼의 입력 데이터에 각각 5번, 2번 연산했고, 비밀번호 알아맞추기 예시에서는 10_000만큼의 입력 데이터에 각각 10_000번, 14번의 연산을 했다.

결론 : 데이터가 정렬되어 있다면, 또 입력 데이터의 양이 커지면 커질 수록, 이진 탐색을 이용하는 것이 효율적이다.