알고리즘 개념 및 용어정리 (시간복잡도, 공간복잡도, 재귀함수)

 

 

 

# 알고리즘 비교 방식

 

 

1>   시간 복잡도 (Time Complexity) 

 

- 같은 크기의 데이터를 처리하는데 상대적으로 오래 걸리는 알고리즘을 시간 복잡도가 크다고 한다.

 

- Big-O 점근 표기법 (n이 크다는 가정하에 다른 숫자는 무시하고 표기)

 

 

 

# 시간 복잡도 (Time Complexity) : Input 크기에 비례하는 알고리즘 실행시간

 

 

- O(1) 시간복잡도 함수

 

1. type 함수 경우 데이터 타입 리턴 (type(4) -> 'int')

2. len 함수 경우 길이 리턴 (len(list))

3. append 함수 경우 리스트 끝에 값 추가 (append(2))

 

- max, min 함수 경우 파라미터 개수만큼 탐색 : O(n)

 

 

 

# 공간 복잡도 (Space Complexity) : Input 크기에 비례해서 알고리즘이 사용하는 메모리 공간

 

 

- 공간 복잡도도 O(1), O(n), O(n2)... 등 빅오표기법으로 표현 가능

 

 

 

- O (1) 시간

1. 배열 색인 액세스 (int a = ARR [5];)
2. 연결된 목록에 노드 삽입
3. 스택에서 푸시 및 POP
4. 대기열에서 삽입 및 제거
5. Array에 저장된 트리에서 노드의 부모 또는 왼쪽 / 오른쪽 자식 찾기

 

 

 

- O (n) 시간

1. 배열 탐색
2. 연결된 목록 탐색
3. 선형 검색
4. 링크 된 목록의 특정 요소 삭제 (정렬되지 않음)
5. 두 문자열 비교
6. Palindrome 확인하기
7. 카운팅 / 버킷 정렬

 

-> 선형성을 필요로하는 모든 Brute Force Algorithms 또는 Noob 알고리즘은 O (n) 시간 복잡도에 기반합니다

 

 

 

- O (log n) 시간

1. 바이너리 검색
2. 이진 검색 트리에서 최대 / 최소 수 찾기
3. 선형 기능을 기반으로하는 특정 분할 및 정복 알고리즘
4. 피보나치 수 계산 – 가장 좋은 방법

 

-> 여기서 기본적인 전제는 전체 데이터를 사용하지 않고 반복 할 때마다 문제 크기를 줄이는 것입니다

 

 

 

- O (nlogn) 시간

1. 병합 정렬
2. 힙 정렬
3. 빠른 정렬
4. O (n ^ 2) 알고리즘 최적화에 기반한 특정 분할 및 정복 알고리즘

 

 

-> ‘log n’의 요소는 Divide and Conquer를 고려하여 도입되었습니다. 이러한 알고리즘 중 일부는 가장 최적화 된 알고리즘으로 자주 사용됩니다.

 

 

 

- O (n ^ 2) 시간

 

1. 버블 정렬
2. 삽입 정렬
3. 선택 정렬
4. 간단한 2D 배열 탐색

 

-> 이 객체들은 O (nlogn) 대응 객체가있을 경우 덜 효율적인 알고리즘으로 간주된다고 합니다.

일반적인 응용 프로그램은 여기서 Brute Force 일 수 있습니다.

 

 

 

# 재귀함수 (반복문의 반복 함수와 다른방식의 반복 호출방식)

 

- 지나친 재귀함수 호출은 stack 이 쌓여 stack overflow 오류가 발생할 수 있습니다.  

 

 

 

# Greedy Algorithm (탐욕 알고리즘)

 

- 당장 최적의 선택을 하는 방식의 알고리즘

- 장점은 구현이 쉽고, 빠르다.

- 단점은 최적의 답이 아닐 수 있습니다.