본문으로 건너뛰기
실습하기

알고리즘의 복잡도(Complexity)란?

알고리즘의 복잡도는 알고리즘이 얼마나 효율적인지를 측정하는 방법으로, 알고리즘의 효율성은 빅 오 표기법(Big O notation)으로 표현합니다.

  • 'O' (Big O): '차수(Order)'를 뜻하며, 알고리즘의 시간 복잡도나 공간 복잡도를 표현합니다. 'O'는 'Order of' 즉, '...의 차수'라는 의미로, 알고리즘이 입력 크기에 대해 얼마나 많은 계산이나 메모리가 필요한지를 나타내는 상한선을 표현합니다.

  • 'n': 일반적으로 알고리즘의 입력 크기를 나타내는 변수입니다.

예를 들어 'O(1)'은 알고리즘의 실행 시간이 입력 크기와 관계없이 일정한 것을 뜻하고, 'O(n)'은 알고리즘의 실행 시간이 입력 크기에 선형적으로 비례하는 것을 나타내며, 'O(n²)'은 입력 크기의 제곱에 비례하여 실행 시간이 기하급수적으로 증가함을 의미합니다.


알고리즘의 복잡도 평가​

알고리즘의 복잡도는 시간 복잡도와 공간 복잡도 두 가지 측면으로 평가힙니다.

  1. 시간 복잡도 (Time Complexity): 알고리즘이 문제를 해결하는 데 걸리는 시간이 얼마나 되는지를 나타냅니다. 일반적으로 입력 크기에 따라 얼마나 많은 단계가 필요한지로 측정됩니다. 예를 들어 간단한 반복문은 입력 크기에 비례하는 '선형 시간 복잡도(O(n))'를 가지며, 중첩된 반복문은 '제곱 시간 복잡도(O(n²))'를 갖습니다.

  2. 공간 복잡도 (Space Complexity): 알고리즘이 실행될 때 필요한 메모리 공간의 양을 뜻합니다. 예를 들어, 고정된 수의 변수만을 사용하는 알고리즘은 '상수 공간 복잡도(O(1))'를 가지며, 입력 크기에 비례하는 추가 메모리가 필요한 경우 '선형 공간 복잡도(O(n))'를 가집니다.


다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!