[자료구조/알고리즘] Big O 빅 오

이전에 파이썬 공부를 하면서 [빅오,자료형] 에 대해 정리를 한적이 있다. 빅오가 무엇이고 빅오 표기법의 종류, 상한과 최악에 대한 글을 작성하였다. 이번 포스팅 에서는 빅오 표기 규칙과 시간 복잡도를 구하는 방법에 대해 공부해 정리해보겠다.

 

빅오를 표기하기 위해서는 알고리즘의 처리해야 할 데이터의 수 n에 대한 연산횟수 f(n)을 구하여 빅오를 구한다.

각 알고리즘의 연산 획수 함수끼리 비교하지 않고 빅오를 계산 하는 이유는 데이터의 수가 많아짐에 따른 연산횟수의 증가 정도가 더 중요하기 때문이다.

빅오 표기법 규칙

1. 계수 법칙 : "상수를 제거하라"
   • 상수 k >0 , f(n)이 O(g(n)) 이면 kf(n)은 O(g(n))이다. n이 충분히 크기 때문에 상수항을 무시해도 되기 때문.
   • 다음의 경우를 비교해보자

   // 1번 : f(n) = n
   function f(n){
   	let count=0;
   	for(let i=0;i<n;i++) count+=1;
   	return count;
   }
   
   // 2번 : f(n) = 5n
   function f(n){
   	let count=0;
   	for(let i=0;i<5*n;i++) count==1;
   	return count;
   }
   
   // 3번 : f(n) = n+1
   function f(n){
   	let count=0;
   	for(let i=0;i<n;i++) count+=1;
   	count+=3;
   	return count;
   }

   1번의 경우는 count에 숫자를 n번 더하기 때문에 시간 복잡도는 O(n)이다.하지만, n이 아주 크게 커질 경우 4번의 연산이 추간된다고 해서 크게 달라지는 것은 없디 때문에 2번의 경우 상수항을 무시하고, 시간 복잡도는O(n)이라고 할 수 있다.
2. 3번의 경우는 마지막 연삭 n+3에 의해 f(n)=n+1 이다. 하지만, n이 커질수록 상수항은 무시가 가능하므로 3번 시간 복잡도 또한 O(n)이다.
3. 2번의 경우는 반복문을 5n번 시행하기 때문에 f(n)=5n이다.

2. 합의 법칙 : "빅오를 더하라"
   • f(n)이 O(h(n))이고 g(n)이 O(p(n))이라면 , f(n)+g(n)은 O(h(n)+p(n))이다.
   • 단순히 알고리즘에 포함되어있는 두 개의 알고리즘의 합니다.
   • 주의 : 합의 법칙을 적용한 다음 계수 법칙을 적용해야 한다.
   • 다음 코드를 통해 확인해보자

   function f(n){
   	let count=0;
   	for(let i=0;i<n;i++) count+=1;
   	for(let i=0;i<5*n;i++) count+=1;
   	return count;
   }

   첫 번째 반복문은 f(n)=n에 해당되고 두 번째 반복문은 g(n)=5n 이다. f(n) + g(n) = 6n이다. 계수법칙을 적용하면 O(n)=n이 된다.

 

3. 곱의 법칙 : "빅오를 곱하라"
   • f(n)이 O(h(n))이고 g(n)이 O(p(n))이면 f(n)g(n)은 O(h(n))p(n))이다.
   • 아래의 코드를 통해 확인해보자

   function f(n){
   	let count=0;
   	for(let i=0;i<n;i++){
   		count+=1;
   		for(let j=0;j<5*n;i++) count+=1;
   	}
   	return count;
   }

   첫 번째 반복문은 f(n)=n 이고 두 번째 반복문의 식은g(n)=5n 이다. 내부에 반복문이 있으므로 f(n)g(n)= 5n^2 이다. (5n^2 번의 연산이 일어난다) 마지막으로 계수의 법칙을 적용하면 O(n)=n^2이 되다.

 

4. 다항 법칙 : "빅오의 k승"다항 법칙은 다항 시간 복잡도가 동일한 다항 차수를 지닌 빅오 표기법을 지닌다.
   • f(n)이 k차 다항식이면 f(n)은O(n^k)이다.$a_m{n}^m+a_{m-1}{n}^{m-1}+a_{m-2}{n}^{m-2}+...+a_1{n}^1+a_0$ →$O(n^m)$
   • 아래의 코드틑 통해 확인해 보자.

   function f(n){
   	let count=0;
   	for(let i=0;i<n*n;i++) count+=1;
   	return count;
   }

   
   
   
5. 반복문의 n*n회 실행되므로 f(n)=n^2이다. 빅오는 O(n)=n^2이다.

시간 복잡도 분석

아래의 코드들에 대한 시간 복잡도를 분석해보자

1. 선형 탐색

function Lsearch(arr,target){
	let i=0;
	for(let i=0;i<arr.length;i++){
		if(arr[i]===target) return true
	}
}

• 위의 함수는 단순한 순차 탐색 알고리즘을 적용한 예이다. 선형 탐색은 배열의 인덱스에 한 번씩 접근하면서 동작한다. 위의 코드에서 사용되는 연산은 < , ++ , === 이 있지만 가장 핵심이 되는 연산은 ===이다. 동등 연산의 수행 횟수가 줄어들면 다른 연산이 줄어들게 되게 때문이다.

• Worst Case(최악의 경우) 알고리즘의 성능을 판단하는데 있어서 중요한 것은 "최악의 경우" 이다. 최선의 경우는 관심의 대상이 아니며 평균적인 경유는 복잡하고 다양한 자료들이 광범위하게 필요하게 되므로 최악의 경우를 고려한다.선형 탐색의 경우 최악의 경우는
  데이터의 수가 n개일 때, 비교연산의 횟수는 n이다.
• f(n)=n ,여기서 f(n)은 최악의 경우를 대상으로 정의한 함수이다.

• 선형탐색은 배열이 정렬되어있지 않을 때 유용하다.

 

2. 이진 탐색(Binary Search)

• 배열을 대상으로 이진 탐색 알고리즘을 적용할 경우 : ' 배열에 저장된 데이터는 정렬되어 있어야 한다'

• 중간 값이 찾는 값과 일치하는지 확인하고 아닌 경우 그 범위를 반씩 줄이는 알고리즘이다.

function binarySearch(arr,target){
    let first=0;
    let last=arr.length-1;
    let mid;

    // first갸 last보다 크면 종료
    while(first<=last){
        mid=Math.floor((first+last)/2);
        if(arr[mid]===target) return true;
        arr[mid]>target ? last=mid-1 // last, first = mid 로 하면 무한푸프를 돈다
        : else first=mid+1 
    }
    return false

 

• Worst Case
  • 연산 횟수를 대표하는 연산 : arr[mid]===target
  • 데이더의 수가 n개일 때 최악의 경우에 발생하는 비교연산의 횟수?
    • n이 1이 되기까지 2로 나눈 횟수 k회
    • 데이터가 1이 남았을 때 마지막으로 비교연산 1회 진행
    • 최악의 경우에 대한 시간 복잡도 : f(n)=k+1
  • n이 1이 되기까지 2로 나눈 횟수가 k이므로, n x (1//2)^k=1 —> k=logn (여기서, log의 밑은 2이다)
  즉, f(n)=log(n)+1이 되고 계수법칙에 의해 O(log(n))이 된다.
•  
• 이진탐색 알고리즘은 데이터의 수가 증가 할수록 지수적으로 증가한다.

 

Uploaded by Notion2Tistory v1.1.0