알고리즘 정의와 분석 방법

1. 알고리즘 정의 

"어떤 종류의 문제를 풀기 위한 방법", " 어떤 종류의 문제를 컴퓨터를 사용하여 해걀하기 위한 효율적인 방법"

--> " 주어진 조건에서 컴퓨터를 사용하여 효율적으로 문제를 해결하는 방법"

---

2. 알고리즘의 표기 방법

O표기법: 알고리즘의 성능을 평가하기 위해 처리해야 할 데이터의 양에 대한 실행 시간을 수학적으로 계산하는 방법, 최악의 성능에 대한 측정 방법

 

출처: stackoverflow

• O(1): 데이터의 양과 무관, 항상 일정한 실행 시간을 가짐
• O(N): 실행시간이 처리해야 하는 데이터 양(N)과 비례함
• O(logN): 데이터 양이 증가하면 실행시간도 증가. 하지만 logN의 그래프를 갖기 때문에 급격한 증가는 아님, 효율적인 검색 알고리즘의 성능
• O(NlogN): 정비례보다 약간 더 증가. 효율적인 정렬 알고리즘의 성능 
• O(N^2): 반복문 2개가 중첩, 좋은 알고리즘은 아님
• O(N^3): 반복문 3개가 중접, 좋은 알고리즘 아님
• O(2^N): 데이터 증가에 따라 2^N만큼의 실행 시간 증가. 그닥......

---

3. 알고리즘에 따른 O 표기법

알고리즘의 성능을 좌우하는 요소는 제어문

 

• 반복문의 최대 반복 횟수로 계산
• 중첩된 반복문은 중텁문의 최대 반복 횟수를 곱셈하여 계산
• 2개 이상 떨어진 반복문은 그 중 가장 큰 값으로 계산
• if-else문은 알고리즘의 성능에 영향을 미치지 않음
• 재귀 호출은 풀어서 계산 - 재귀함수가 호출된 만큼

 

 

4. 알고리즘 최적화

알고리즘의 전체 성능의 O표기법을 구하고, 그 O 표기법의 성능을 높이는 방법으로 최적화 진행 

(중첩된 반복문의 횟수를 줄인다 등) 

---

출처:

자바와 함께하는 자료구조의 이해

https://github.com/WeareSoft/tech-interview

https://www.youtube.com/channel/UCJ4SXKMLQucqaxt4A6PonwQ

필수 알고리즘 with 파이썬