복잡도 (Complexity)

복잡도 (Complexity)

‘이것보다 더 효율적인 문제 해결 방법이 없을까?’

1. 공간 복잡도 : 알고리즘이 실행되는 동안 사용하는 메모리 공간을 측정하는 지표
   • 배열의 크기, 동적 할당 여부, 재귀 함수 등이 영향을 준다.
   • 해결 방법 : 데이터 구조 최적화, 메모리 풀링(=객체 재사용), 압축 기술
2. 시간 복잡도 : 알고리즘이 데이터를 처리하는 데 걸리는 시간을 측정하는 지표
   • 빅오 표기법을 가장 자주 사용한다. → 빅오 표기법은 최악의 경우의 시간 복잡도를 고려하기 때문 (여기서 말하는 최악의 경우란? 이 정도 시간까지 걸릴 수 있다는 의미)
     
   • 해결 방법 : 코드 최적화, 메모이제이션, 병렬 처리

빅오 표기법 (Big-O Complexity)

: 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 증가하는지 상대적인 증가율을 나타낸다.

• 사용 목적

  알고리즘 간 성능 비교/효율성 평가 시 많이 사용
  

• 빅오 계산하는 방법

  • 상수항 무시 - 예시 : O(N+3) = O(N)
  • 입력 크기가 클 때 계수 무시 - 예시 : O(2N) = O(N)
  • 최고차 항만 표기 - 예시 : O(N^2+4N+2) = O(N^2)

• 빅오 표기법 비교

  **O(1) < O(㏒ N) < O(N) < O(N ㏒ N) < O(N²) < O(2ⁿ)**

  

  • O(1): 상수 시간.
    • 예시: 배열 인덱스 접근, Stack의 push와 pop
  • O(㏒ N): 로그 시간.
    • 예시: 이진 탐색
  • O(N): 선형 시간.
    • 예시: for 문 순차 탐색
  • O(N ㏒ N): 보통 효율적인 정렬 알고리즘에서 발생.
    • 예시: 퀵 정렬, 합병 정렬, 힙 정렬
  • O(N²): 이차 시간 복잡도.
    • 예시: 삽입 정렬, 버블 정렬, 선택 정렬, 이중 for 문
  • O(2ⁿ): 지수 시간.
    • 예시: 피보나치 수열
  • O(n!): 팩토리얼.
    • 예시: 순열, 완전탐색

• 정렬의 시간복잡도

  

• 자료구조의 시간복잡도

  

[ APS 팁 ]

• 실제 알고리즘 풀이할 때
  • 시간복잡도 따지는 법 : 데이터의 크기 + 제한 시간 확인
    • 제한 시간 1초 = 1억번의 연산 안에 답이 나와야한다.
    • 연산 횟수 = (알고리즘 시간복잡도 * 데이터의 크기)
  • 시간복잡도 줄이는 법 :
    1. 반복문 수 줄이기 (or 반복문 내 담색 범위 줄이기)
    2. 조건문 줄이기
    3. 자료구조 적절히 활용 (DP, 비트마스킹 등)
    4. 알고리즘 적절히 활용 (그리디, DP, 비트마스킹, 이진 탐색, 투포인터 등)

[ CS 면접 ]

• 시간 복잡도와 공간 복잡도가 무엇인가?
• 꼬리질문) 각 알고리즘 별 시간 복잡도
  • 에시 : 정렬의 최선/최악 시간복잡도