알고리즘
알고리즘은 특정 문제를 해결하기 위한 잘 정의된 지침 세트 또는 단계별 절차이다. 컴퓨터 프로그래밍에서 알고리즘은 데이터를 조작하고, 계산을 수행하고, 작업을 자동화하는 데 사용된다.
알고리즘의 조건
- 명확성: 각 단계가 명확하고 잘 정의되어 있어야 함
- 입력: 0개 이상의 입력을 받음
- 출력: 1개 이상의 출력을 생성
- 유한성: 유한한 수의 단계 후에 종료
- 효과: 각 단계는 사람이 연필과 종이만 사용하여 수행할 수 있을 만큼 기본적이며 단순해야 함
시간 복잡도
시간 복잡도는 알고리즘이 완료되는 데 걸리는 시간을 측정한 것이다. 이는 알고리즘의 실행 시간을 추정하여 코드의 효율성과 확장성을 결정하는 데 도움이 되며, 시간 복잡도는 일반적으로 Big-O 표기법을 사용하여 표현된다.
공간 복잡도
공간 복잡도는 알고리즘에 필요한 메모리 공간의 양을 측정한다. 변수, 데이터 구조 및 함수 호출을 위한 공간을 포함하여 알고리즘에서 사용하는 메모리 공간의 총량을 고려하며, 시간 복잡도와 마찬가지로 공간 복잡도도 일반적으로 Big-O 표기법을 사용하여 표현된다.
빅오 표기법
Big-O 표기법은 알고리즘의 시간 복잡도 또는 공간 복잡도를 설명하는 데 사용되는 수학적 표기법이다. 효율성과 확장성 측면에서 알고리즘에 대한 높은 수준의 이해를 제공한다.
- O(1): 상수 시간
- 입력 크기와 관계없이 실행 시간이 일정하게 유지된다.
- 예시: 인덱스를 통해 배열의 특정 요소에 액세스한다. 배열의 크기와 관계없이 이 작업에는 항상 같은 시간이 걸린다.
- O(log n): 로그 시간
- 실행 시간은 입력 크기에 따라 로그적으로 증가한다.
- 예시: 정렬된 배열의 이진 검색. 각 단계는 검색 공간을 절반으로 줄이므로 검색 시간은 입력 크기에 따라 로그적으로 늘어난다.
- O(n): 선형 시간
- 실행 시간은 입력 크기에 따라 선형적으로 증가한다.
- 예시: 목록의 각 요소를 하나씩 확인하는 선형 검색. ‘n’개의 요소가 있는 경우 최악의 경우 ‘n’개의 요소를 모두 확인해야 할 수도 있다.
- O(n log n): 선형 시간
- 병합 정렬 및 힙 정렬과 같은 정렬 알고리즘에서 나타난다.
- 예시: 이러한 정렬 알고리즘은 선형 및 로그 성장률을 결합하여 대규모 데이터 세트를 정렬하는 데 효율적이다.
- O(n^2): 2차 시간
- 데이터에 대한 중첩 루프가 있는 알고리즘에서 자주 볼 수 있다.
- 예시: 버블 정렬, 삽입 정렬 또는 선택 정렬. 이러한 정렬 알고리즘에는 데이터에 대한 중첩 루프가 포함되어 있어 정렬에 2차 시간 복잡성이 발생한다.
- O(2^n): 지수 시간
- 입력 데이터가 추가될 때마다 실행 시간이 두 배로 늘어난다.
- 예시: 피보나치 수열 계산. 함수가 각 호출에 대해 자신을 두 번 호출하여 호출 수가 기하급수적으로 증가한다.
- O(n!): 계승 시간
- 입력 크기가 계승적으로 증가한다.
- 예시: 무차별 검색을 통해 여행하는 외판원 문제 해결. 여기에는 ‘n’ 도시를 방문하는 가능한 모든 순서를 확인하는 작업이 포함되며, 이는 ‘n’에 따라 계승적으로 증가한다.