간단하게 정리한 빅오표기법

알고리즘

알고리즘은 어떤 문제를 해결하기 위한 여러 동작들의 모임을 말합니다. 다시 말해 어떤 값을 입력받아 결과 값을 출력하는 절차를 의미합니다. 이러한 문제 해결에 필요한 조건은 다음과 같습니다.

• 입력 : 0개 이상의 입력(외부) 데이터가 존재해야 한다.
• 출력 : 1개 이상의 결과가 존재해야 하며 중복되지 않은 2개 이상의 결과가 있어야 한다.
• 유한성 : 모든 과정 및 명령은 유한한 범위에서 실행과 종료 해야한다.
• 효율성 : 모든 과정은 명백히 실행 가능한 범위에 있어야 한다.
• 명확성 : 수행과정은 명확해야 한다.

좋은 알고리즘이란?

좋은 알고리즘이란 처리 시간이 짧고, 사용 메모리가 적은 것을 말합니다. 우리는 두가지 조건을 각각 시간 복잡도, 공간 복잡도라 말합니다.

시간 복잡도는 알고리즘을 수행하는데 평균, 최악의 경우 얼마만큼의 수행 시간이 발생하는지를 말하고 공간복잡도는 알고리즘을 수행하는데 얼마만큼의 메모리를 사용하는지를 의미합니다.

이러한 복잡도를 표기할 때 우리는 보통 빅오 표기법을 사용해서 나타냅니다. 빅오 표기법은 알고리즘의 복잡도(빠르기)를 단순화할 때 사용되는 대표적 표기법이며 연산 횟수를 기준으로 하기 때문에 속도를 시간단위로 세지 않는 특징을 가지고 있습니다.

빅오표기법

빅오표기법은 시간 복잡도 알고리즘에 불필요한 연산을 제거해 알고리즘 분석을 조금 더 간편하게 할 목적으로 시간 복잡도를 표기하는 방법입니다.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

O(log n)	O(n)	O(n log n)	O(n²)	O(n!)
이진탐색	단순탐색	퀵정렬	선택정렬	외판원문제

시간복잡도에서 가장 중요한 부분은 n의 단위입니다. 상수는 알고리즘이 소비하는 어떠한 특정 시간으로 불리는데 예를 들어 두 개의 알고리즘이 서로 다른 빅오 표기법의 시간을 가지는 조건에서는 상수는 크게 문제가 되지 않습니다.

단순 탐색 : 10밀리초 * n

이진 탐색 : 1초 * log n

위와 같이 알고리즘의 처리속도가 존재할 때 단순히 보기엔 단순 탐색이 훨씬 더 빠르다고 생각할 수 있습니다. 하지만 40억개의 원소를 가진 리스트를 탐색한다고 가정했을때 걸리는 시간은 다음과 같습니다.

단순탐색 : 10밀리초 * 4,000,000,000 = 463초

이진 탐색 : 1초 * 32 (log n) = 32초

데이터의 양이 많아지는 조건에서는 이진 탐색이 훨씬 빨라지는 것을 알 수 있으므로 상수는 전혀 문제가 되지 않는 것을 확인할 수 있습니다. (가끔 예외적인 경우 -> 퀵 정렬과 병합 정렬)

문제 해결 단계

• O(1) : 상수시간
  • 문제를 해결하는데 한 단계 처리
• O(log n) : 로그시간
  • 문제를 해결하는데 필요한 단계들이 연산을 거듭할수록 특정 조건에 의해 감소
  • 입력의 크기에 따라 연산 횟수가 줄어드는 케이스
• O(n) : 직선시간
  • 문제를 해결하기 위한 단계수와 입력값 n이 1:1 로 동일
  • Ex : 배열의 길이만큼 반복하는 케이스
• O(n log n) : 선형로그
  • 문제를 해결하기 위한 단계수가 n * log₂N 만큼 가짐
• n² : 2차 시간
  • 문제를 해결하기 위한 단계수는 n의 제곱
  • Ex : 반복문이 두번 있는 케이스

Reference

• 그림으로 개념을 이해하는 알고리즘
• https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://opentutorials.org/course/2471/13912
• https://madplay.github.io/post/time-complexity-space-complexity
• https://brenden.tistory.com/2
• https://www.youtube.com/watch?v=Y7KTRu6-XK0
• https://blog.chulgil.me/algorithm/