알고리즘 시작전 알면 좋은 기초 개념 정리

빅오표기법

알고리즘이 얼마나 빠른지에 대한 표시방법입니다.

연산횟수를 기준으로 하기 때문에 속도를 시간단위로 세지 않으며 빅오표기법은 최악의 경우에 대한 기준으로 합니다.

실행 시간

선형시간

계산복잡도 이론상 에서 입력의 길이 n에 대해 특정 알고리즘의 실행시간이 선형의 특징을 가지는 것을 말합니다. 예를 들어 100의 길이를 가진 원소를 단순탐색으로 자료를 확인한다면 100번의 횟수를 확인해야 하고 이때 걸리는 시간을 선형시간이라 말합니다.

로그시간

정렬된 리스트를 이진탐색 사용시 원소의 log₂N번의 횟수로 자료를 찾을 수 있습니다. log₂8 -> 3회, log₂32 -> 5회, log₂1024 -> 10회 이진탐색의 경우 로그시간으로 실행됩니다.

알고리즘 속도

• 알고리즘의 속도는 시간이 아니라 연산 횟수에 의한 측정

• 알고리즘의 실행 시간은 빅오 표기법을 사용

표기법

• n은 연산 횟수를 뜻합니다.

단순탐색

• n번의 횟수, 하나씩 확인 -> O(n)
  • ex) O(16) = 16회

이진탐색

• Log n번 확인 -> O(log n)
  • ex) O( log₂16) = 4

이진탐색은 정렬된 상태에서 사용 가능합니다. 리스트에 원하는 데이터가 있으면 데이터의 위치를 반환하고 없으면 null을 반환합니다.

1. 1~100 사이에 숫자를 하나를 생각합니다.
2. 범위를 절반을 기준으로 줄여나갑니다. (100 - 50 - 25 - 13 - 7 - 4 - 2 - 1)
3. 최대 7단계

처음부터 순차적으로 탐색하는 단순 탐색은 위와 같은 범위를 가질 때 최대 99번을 반복해야 찾을 수 있기에 효율적이지 못합니다.

log₂N

n개의 데이터를 가진 리스트에 이진 탐색을 사용할 시 최대 log₂N번의 횟수가 발생합니다.

log란 거듭 제곱의 반댓말로 log₂ 8일때 2 * 2 * 2 = 3번의 횟수를 의미합니다.

배열 및 연결리스트

모든 원소의 값을 한 번에 읽어야 한다면 연결리스트, 특정한 원소만 알고 싶다면 모든 원소 주소를 다 알고 있는 배열이 유리합니다.

원소를 가운데 삽입할 때 연결리스트는 이전 원소가 무엇을 가리키는지만 바꾸면 되고 배열은 모든 원소의 위치를 바꿔야 하기 때문에 리스트가 더 유리하고 삭제도 마찬가지로 배열에서는 한 요소를 삭제한다면 나머지 요소들을 이동해줘야하기 떄문에 리스트가 더 적합합니다.

자료 접근 방식

• 임의접근
  • 배열 (순차적이 아니라 찾고자 하는 요소로 바로 건너 읽기)
    • 읽기 속도가 빠름
• 순차접근 (원소를 첫번째부터 순차적으로 하나씩 읽기)
  • 연결리스트

정렬 알고리즘 비교

알고리즘	최선	평균	최악
Bubble Sort	O(n)	O(n²)	O(n²)
Heap Sort	O(n log n)	O(n log n)	O(n log n)
Insertion Sort	O(n)	O(n²)	O(n²)
Merge Sort	O(n log n)	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n log n)	O(n²)
Selection Sort	O(n²)	O(n²)	O(n²)
Shell Sort	O(n)	O(n log n²)	O(n log n²)
Smooth Sort	O(n)	O(n log n)	O(n log n)

알고리즘의 종류

• 재귀
• 정렬
• 탐색
• 해시
• 그래프

Reference

• 그림으로 개념을 이해하는 알고리즘
• 위키백과