[알고리즘] 알고리즘 Algorithm

 

---

 

1. 알고리즘

• 문제 해결을 위한 명확한 절차나 규칙의 결합
• 알 쾨리즈미의 이름에서 유래
• 컴퓨터가 작업을 자동화하고 효율적으로 수행하도록 지시
• 시간 복잡도, 공간 복잡도(메모리 사용량) 등의 척도로 성능 평가

 

2. 알고리즘의 특징

• 유한성: 반드시 종료되어야 함
• 명확성: 각 단계가 명확히 정의되어 일관적인 결론이 도출되어야 함
• 입력과 출력: 최소 1개의 입력과 출력이 필요함
• 효과성: 간 단계는 기본적인 연산으로 수행 가능해야 함

 

3. 시간 복잡도

O(1): 상수 시간

• 입력 크기에 상관없이 일정 시간이 소요됨
• 배열에서 특정 인덱스를 조호하는 작업이 이에 해당
• 가장 효율적인 시간 복잡도로, 입력 크기와 무관해 빠른 실행 시간을 보장

O(log n): 로그 시간

• 입력 크기가 증가할 수록 시간이 느리게 증가
• 이진 탐색 알고리즘이 이에 해당
• 대규모 데이터셋에서도 효율적인 성능을 보임

O(n): 선형 시간

• 입력 크기에 비례하여 시간이 증가
• 배열에서 특정 값을 찾기 위한 선형 탐색
• 중간 정도의 효율성을 가지며 작은 데이터셋에서는 충분함

O(n log n): 로그 선형 시간

• 시간이 입력 크기와 그 로그 값의 곱에 비례
• 병합 정렬, 힙 정렬 등이 이에 해당
• 대규모 데이터 정렬에 효과적인 복잡도

O(n²): 이차 시간

• 입력 크기의 제곱에 비례하여 시간이 증가
• 버블 정렬, 선택 정렬이 이에 해당
• 작은 데이터 셋에서는 사용 가능하지만 큰 데이터 셋에서는 비효율적

O(2^n): 지수 시간

• 입력 크기에 따라 실행 시간이 지수적으로 증가
• 부분집합 생성, 외판원 문제의 완전 탐색 등이 이에 해당
• 매우 비효율적이며 작은 입력 크기에서도 실행 시간이 급격히 증가

 

4. 알고리즘 설계 패러다임

분할 정복(Divide and Conquer)

매우 작은 문제를 부분으로 나누어 해결

동적 프로그래밍(Dynamic Programming)

중복된 계산을 줄이고 문제를 효율적으로 해결

탐욕 알고리즘(Greedy Algorithm)

각 단계에서 최선의 선택을 함