빅 오(Bit-O) 표기법

• 알고리즘의 성능을 수학적으로 표현해주는 표기법.
• 알고리즘의 시간 및 공간복잡도 표시.
• 데이터나 사용자의 증가율에 따른 알고리즘의 성능 예측하는 것이 목표
• 영향력 없는 항이나 상수는 무시
  • O(N² + N) → O(N²)
  • O(2N+1) → O(N)
• 자주 사용되는 빅오 표기법
  • O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
• 프로그램의 성능을 측정하는 방법 중 대표적으로 프로그램 실행시 CPU, RAM 사용량을 측정해볼 수 있음.
  • CPU 사용량 측정 → 시간복잡도 계산
  • RAM 사용량 측정 → 공간복잡도 계산
• 아무리 최악의 상황이더라도 이 정도의 성능을 보장할 수 있다라는 것을 나타내기 위해 빅오 표기법 사용.

O(1)

입력 데이터의 크기에 상관 없이 언제나 일정한 시간이 걸리는 알고리즘

사진

code

F(int[] a) {
    return (a[0]==0)? true: false
}

• 첫번째 배열의 값이 0인지 확인.
• 배열 a의 크기에 상관없이 언제나 일정한 속도로 결과를 반환

O(n)

입력 데이터의 크기에 비례해서 처리시간이 증가하는 알고리즘

code

F(int[] a) {
    for i = 0 to n.length
    	print i
}

• 데이터가 증가함에 따라 처리 시간도 같이 비례 증가함.

O(n²)

입력한 데이터 n의 제곱만큼 처리 시간이 증가하는 알고리즘

code

F(int[] a) {
    for i = 0 to n.length
    	for j = 0 to n.length
    		print i + j;
}

O(N³)

데이터에 양에 비해 3제곱만큼 시간이 증가하는 알고리즘

F(int[] n) {
    for i = 0 to n.length
    	for j = 0 to n.length
    		for k = 0 to n.length
    			print i + j + k;
}

• 좋은 알고리즘이 아님.
• for문 3번 중첩하는 경우.

O(log n)

문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.

F(k, arr, s, e) {
    if(s>e) return -1;
    m = (s + e) / 2;
    if(arr[m] == k) return F(k, arr, s, m-1);
    else return F(k, arr, m+1, e);
}

• 대표적 알고리즘은 이진검색

예제

int sum(int N) {
    return N * N;
}

• 곱셉 연산 1개로, O(1)이 된다.
• 어떤 데이터를 입력해도 동일한 시간으로 계산됨.

int sum2(int N) {
	sum = 0;
	
	for(int i=1; i<=N; i++) {
        sum = sum + N;
	}
	
	return sum;
}

• 덧셈 연산 1개와 대입 연산 1개가 N만큼 실행되므로 2N의 시간이 걸리지만, 상수를 무시하므로 O(N)이 된다.

---