알고리즘 정의

컴퓨터 분야에서 알고리즘이란?

• 주어진 조건(Condition)에서 컴퓨터를 사용하여 효율적으로 문제를 해결하는 방법

알고리즘의 표기 방법

O 표기법 또는 빅 O 표기법

• 알고리즘의 성능 평가 방법 중에서 가장 많이 사용하는 방법
• 최선의 성능, 최악의 성능 중 최악의 선능에 대한 측정 방법
  

1. O(1) : 스택에서 push, Pop

• 처리해야 할 데이터의 양과 상관없이 항상 일정한 실행 시간을 갖는 알고리즘을 의미

2. O(logN) : 이진트리

• 처리해야 할 데이터의 양이 증가할수록 실행 시간도 약간씩 증가하는 알고리즘
• 실행 시간의 증가폭 자체가 log N 그래프를 갖기 때문에 급격하게 증가하지 않음
• 일반적으로 효율이 좋은 검색 알고리즘의 성능이 이에 해당

3. O(N) : for문

• 처리해야 할 데이터의 양과 비례하여 실행 시간도 증가하는 경우

4. O(N log N) : 퀵, 병합, 힙 정렬

• 처리해야 할 데이터의 야에 비해 정비례보다 약간 더 증가하는 실행 시간을 갖게 됨
• 일반적으로 효율이 좋은 정렬 알고리즘의 성능이 이에 해당

5. O(N^2) : 삽입, 거품, 선택 정렬

• 이와 같은 알고리즘은 반복문 2개가 중첩되어 있는 경우의 알고리즘
• 처리해야 할 데이터의 양이 증가하면 증가할수록 데이터의 제곱만큼의 실행 시간이 소요
• 그리 좋은 알고리즘이라 할수 없음

6. O(N^3)

• 반복문이 3번 중첩되어 있는 경우의 알고리즘
• 처리해야할 데이터가 증가하면 실행 시간은 그의 3제곱만큼 증가하기 때문에 상당히 성능이 좋지 않음

7. O(2^N) : 피보나치 수열

• 데이터의 증가에 따라 2의 N승 만큼의 실행 시간이 증가하는 알고리즘
• 그다지 추천하지 않음