[알고리즘] 시간 복잡도 (Time Complexity)

개요

 

코딩테스트 스터디원의 풀이를 보는데 어느 것이 더 프로그래밍 쪽으로 나은 풀이인지 파악이 어려워 기준을 파악해 보고자, 효율적인 알고리즘을 선택하고자 찾아본 개념

 

📍정의

시간 복잡도 : 알고리즘의 입력 크기에 따라 프로세스가 실행되는 데 걸리는 시간을 수치화 한 것

- 컴퓨터의 성능에 따라 실행시간은 달라질 수 있기에, 명령문의 실행 빈도수를 계산하여 실행 시간을 구한다. 

 

 

📍시간복잡도 분석법

• 빅오 표기법 (최악의 경우): 최악의 입력이 주어졌을 경우의 알고리즘이 수행하는 연산의 수 측정
• 세타 표기법 (평균의 경우) : 모든 입력이 주어졌을 떄의 평균으로 걸리는 시간 측정
• 오메가 표기법 (최선의 경우) : 가장 유리한 입력이 주어졌을 때의 알고리즘이 수행하는 연산의 수 측정

 

 

📍빅오 표기법(Big-O)

빅오 표기법 : 알고리즘의 실행 시간이 입력 데이터의 크기 n에 대해서 어떻게 변하는지 나타내는 방법

 

📍종류 & 예시

• 상수 시간 복잡도 O(1) : 입력 크기와 상관없이 일정한 시간 소요
  • 배열에서의 특정 인덱스 접근
  • 해시 테이블
• 로그 시간 복잡도 O(log n) : 입력 크기가 증가할수록 실행 시간이 느리게 증가
  • 이진탐색
• 선형 시간 복잡도 O(n) : 입력 크기에 비례하여 시간 증가
  • 배열의 모든 요소 순회 
• 선형 로그 시간 복잡도 O(n log n)
  
  • 병합 정렬, 퀵 정렬
• 이차 시간 복잡도 O(n^2) : 입력 크기가 증가함에 따라 실행시간이 제곱에 비례하여 증가
  • 반복문이 두 번 있는 구조
  • 버블 정렬, 선택 정렬

 

📍시간 복잡도의 중요성

• 효율적인 알고리즘 선택
• 실행 시간 예측 가능