[알고리즘] 복잡도, 빅오(Big-O) 표기법

알고리즘

어떠한 주어진 문제를 풀기위한 절차나 방법을 말한다. 컴퓨터 프로그램을 기술함에 있어 실행 명령어들의 순서를 의미한다.

 

조건

• 입력 : 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.
• 출력 : 알고리즘은 최소 1개 이상의 결과를 가진다.
• 유한성 : 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다.
• 명확성 : 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.
• 효과성 : 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간안에 정확하게 수행할 수 있을 정도로 충분히 단순해야한다.

 

종류 / 문제유형

그리디 알고리즘 (욕심쟁이 알고리즘, Greedy Algorithm)

현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법

 

구현 (Implementation)

머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기

 

DFS / BFS 

그래프를 탐색하기 위한 대표적인 두 가지 알고리즘

 

정렬

연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘

 

이진 탐색

탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘

참고 링크 >>> 이진트리(Binary Tree) - 이진탐색

 

분할 정복법 (Divide and Conquer)

여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념

 

동적 계획법 (다이나믹 프로그래밍, Dynamic Programming : DP)

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 (접근 방식은 기본적으로 분할 정복 알고리즘과 비슷) 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 (ex. 피보나치 수열)

 

최단경로

특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘

 

백트래킹 (BackTracking)

모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식으로, 일종의 트리탐색 알고리즘이라고 봐도 된다.

 

 

복잡도

알고리즘의 성능을 나타내는 척도

시간 복잡도

알고리즘을 위해 필요한 연산의 횟수 (얼마나 오래걸리는 지)

공간 복잡도 

알고리즘을 위해 필요한 메모리의 양

 

효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립한다. 메모리를 더 사용하는 대신 반복되는 연산을 생략해서 시간을 비약적으로 줄이는 방법으로 메모이제이션 (Memoization) 기법이 있는데, 피보나치 수열 등 재귀함수를 사용하는 문제에서 '시간 초과 Time Limit Exceeded' 를 피하기 위해 사용할 수도 있다. 

 

예) Fibonacci Number (JAVA)

배열에 기존 연산결과를 저장하는 방식으로, 메모리는 더 사용하지만 이전 연산작업을 재수행하지 않아도 된다는 이점이 있다. 다시 처음부터 연산 할 필요없이, 배열에 저장된 기존 연산값을 사용하여 시간을 줄인다.

 

 

빅오(Big-O) 표기법

빅오 표기법	명칭
O(1)	상수 시간(Constant time)
O(logN)	로그 시간(Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차 시간
O(N³)	삼차 시간
O(2ⁿ)	지수 시간

시간 복잡도를 표현할 때는 빅오표기법을 사용한다.

선형 복잡도 : 입력 자료를 하나씩 모두 처리 (ex. 순차 탐색)

• O(1) : 상수형 복잡도. 자료 크기와 무관하게 항상 같은 속도 (ex. 해시 함수)
• O(logN) : 로그형 복잡도. (ex. 이진 탐색)
• O(N) : 입력 자료의 크기 N에 대하여 대략 크기 N에 비례하는 수의 연산을 수행
• O(NlogN) : 선형 로그형 복잡도. (ex. 퀵 정렬, 힙 정렬, 병합 정렬)
• O(N²) : 제곱형 복잡도. 루프 구조. 이중 for문. (ex. 선택 정렬, 버블 정렬, 삽입 정렬)

 

정렬 알고리즘의 시간 복잡도 ?

'선택 정렬, 삽입 정렬' 등은 최악의 경우 O(N²)의 시간이 소요되지만 '병합 정렬' 등은 최악의 경우에도 시간복잡도 O(NlogN)을 보장한다. 대부분의 프로그래밍 언어의 라이브러리에서도 O(NlogN)을 보장하는 형태로 정렬 기능을 제공하고 있다.

 

 

 

유투브 참고 : www.youtube.com/watch?v=6Iq5iMCVsXA