빅 오 사용법
선형 검색의 최악의 경우 배열의 크기인 N 만큼 단계가 필요하다. 이를 빅 오로 표현하게 되면, O(N)이라고 표현 할 수 있다.
빅 오 N = 차수 N = 오 N라고 발음 할 수 있다.
선형 검색은 O(N)이라고 표현 한다. 그렇기에 O(N)인 알고리즘을 선형 시간을 갖는 알고리즘이라고 부른다.
그렇다면 배열의 읽기, 1단계 만을 필요하는 프로그램은 어떻게 표현 할 수 있을까???
답은 O(1)이다. 즉 배열의 크기와 상관없이 프로그램에서 데이터를 읽는 걸리는 단계는 단 1단계이다.
그렇기에 O(1)을 가장 빠른 알고리즘 유형으로 분류한다. 데이터가 늘어나도 알고리즘의 단계 수는 증가하지 않는다. N이 얼마나 커지든 항상 상수 한 단계만을 필요로 한다. 그래서 O(1)을 갖는 알고리즘을 상수 시간을 갖는 알고리즘이라고 표현한다.
빅 오의 본질
빅오의 본질이란 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.
이러한 관점으로 보게 되면 알고리즘이 O(1)이든 O(3)이든 중요하지 않다. 두 알고리즘 모두 데이터 크기에 영향을 받지 않으므로, 본질적으로 같은 알고리즘 이다.
하지만 O(N) 경우 데이터의 크키가 알고리즘의 효율성과 비례한다.
그림을 보면 O(N) 완벽한 대각선을 그리지만, O(1)은 완벽한 수평선을 그린다. O(N)은 데이터 크기와 비례하고, O(1) 데이터 크기와 전혀 무관하다.
만약 100단계 걸리는 O(1) 알고리즘과 O(N) 알고리즘이 존재 할 원소의 수가 100보다 작다면, O(1) 알고리즘이 효율적이다. 하지만 원소가 100보다 큰 모든 배열에서 O(N) 더 많은 단계를 필요로 한다. 이것은 무한대 까지 증가 할 수 있다.
그렇기에 전박적으로 O(N) 알고리즘 보다 O(1) 알고리즘이 효율적이라 말 할 수 있다.
- 같은 알고리즘 다른 시나리오
선형 검색은 최서의 경우 O(1)번으로 검색을 완료 할 수 있다. 하지만 최악의 경우 O(N) 수행을 필요로 한다. 이 때 선형 검색을 빅 오로 표현 하면 O(N)이라고 표현한다. 그 이유는 최악의 시나리오를 의미하는 비관적인 접근이 유용한 도구로 사용될 수 있기 때문이다. 최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 알면 최악을 대비할 수 있고, 알고리즘 선택의 중요한 영향을 미칠 수 있다.
0000세 번째 유형의 알고리즘
읽기 = O(1) 상수 시간, 선형 검색의 경우 O(N) 선형 시간, 그렇다면 이진 검색은 어떻게 표현 해야 할까?
이진 검색의 경우 한번 검색 단계를 거칠 때 마다 검색해야 하는 데이터 원소 수가 절반씩 줄어든다. 그렇기에 이를 O(logN) 오 로그 N 이라고 표현한다.
로가리즘이란??
왜 이진 검색을 O(logN)이라고 표현하는지 알아보자.
64 = 2^6이다. 이는 log2(64) = 6이다. 8을 생각해보자 8/2/2/2 = 1 이다.
log2(8) = 3 이다 즉 8이하의 5이상의 크기의 배열을 이진 탐색하는데 걸리는 단계는 3단계임을 알 수 있다. 그렇기는 이진 검색을 O(logN)이라고 표현한다.
O(logN)해석
O(logN)은 O(log2(N))이라고 표현 할 수 있다. 이 때 우리는 2를 생략하고 적는다.
로가리즘에 대해서 설명을 하면서, 이진 검색의 빅 오가 O(logN)인지 확인 할 수 있었다.
이진 검색은 특정 항목이 남을 때 까지 배열의 셀을 계속 절반으로 자르면서 범위를 좁혀간다.
간단히 말해서 O(logN)은 원소가 하나가 될 때 까지 데이터 원소를 반으로 줄이는 것이다.
밑에 표를 본다면, O(N)과 O(logN) 성능을 비교 할 수 있다.
코드와 빅 오
이 코드의 빅 오는 모든 리스트에 있는 문자열을 출력해야 하기 때문에 O(N)이라고 말 할 수 있
다.
그렇다면 소수를 구하는 알고리즘의 빅 오는 어떻게 될까?
이 코드는 숫자 n이 주어진다면, n이 소수인이지 확인하기 위해 2이상 n미만의 수로 n을 나눈다.
그렇기 때문에 n이 소수라면 빅 오는 O(N)으로 표현 할 수 있다.
아래 코드는 또 다른 소수를 판단하는 방법이다.public class Eratos { public static void main(String[] args) { // ArrayList로 구현 ArrayList<Boolean> primeList; // 사용자로부터의 콘솔 입력 Scanner scan = new Scanner(System.in); int n = scan.nextInt(); // n <= 1 일 때 종료 if(n <= 1) return; // n+1만큼 할당 primeList = new ArrayList<Boolean>(n+1); // 0번째와 1번째를 소수 아님으로 처리 primeList.add(false); primeList.add(false); // 2~ n까지 소수로 설정 for(int i=2; i<=n; i++ ) primeList.add(i, true); // 2부터 ~ i*i <= n // 각각의 배수들을 지워간다. for(int i=2; (i*i)<=n; i++){ if(primeList.get(i)){ for(int j = i*i; j<=n; j+=i) primeList.set(j, false); //i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다. } } StringBuffer sb = new StringBuffer(); sb.append("{"); for(int i=0; i<=n; i++){ if(primeList.get(i) == true){ sb.append(i); sb.append(","); } } sb.setCharAt(sb.length()-1, '}'); System.out.println(sb.toString()); } }이 경우의 빅 오는 O(NloglogN)이다.
