[알고리즘 공부] * 시간복잡도란?

 

 

 

 

 

 

안녕하세요 오늘은 알고리즘에서 시간복잡도가 무엇인지 왜 중요한지에 대해 알아보겠습니다.

 

시간 복잡도(Time Complexity)는 알고리즘의 성능을 분석할 때 사용하는 개념으로,

입력 크기(input size)에 따라 알고리즘이 실행되는 데 걸리는 시간을 수학적으로 표현한 것입니다.

시간 복잡도는 주로 Big-O 표기법(Big-O Notation)을 사용하여 나타냅니다.

Big-O 표기법은 알고리즘의 최악의 실행 시간을 나타내며,

알고리즘이 얼마나 효율적인지 평가하는 데 사용됩니다.

 

주요 시간 복잡도 유형

 

O(1) - 상수 시간(Constant Time):

입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우입니다.

예: 배열의 특정 인덱스에 접근하는 경우.

 

O(log n) - 로그 시간(Logarithmic Time):

입력 크기가 증가함에 따라 실행 시간이 로그 함수처럼 증가하는 경우입니다.

예: 이진 탐색(Binary Search).

 

O(n) - 선형 시간(Linear Time):

입력 크기에 비례하여 실행 시간이 증가하는 경우입니다.

예: 배열의 모든 요소를 한 번씩 순회하는 경우.

 

O(n log n) - 선형 로그 시간(Linearithmic Time):

입력 크기에 로그를 곱한 만큼 실행 시간이 증가하는 경우입니다.

예: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort).

 

O(n^2) - 이차 시간(Quadratic Time):

입력 크기의 제곱에 비례하여 실행 시간이 증가하는 경우입니다.

예: 이중 루프를 사용하는 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort).

 

O(2^n) - 지수 시간(Exponential Time):

입력 크기에 대해 지수적으로 실행 시간이 증가하는 경우입니다.

예: 피보나치 수열을 재귀적으로 계산하는 경우(단순 재귀).

 

O(n!) - 계승 시간(Factorial Time):

입력 크기에 대해 계승적으로 실행 시간이 증가하는 경우입니다.

예: 외판원 문제(Traveling Salesman Problem)의 브루트 포스 알고리즘.

 

 

시간 복잡도의 중요성

 

시간 복잡도는 알고리즘의 효율성을 평가하는 데 중요한 역할을 합니다.

입력 크기가 커질수록 알고리즘의 실행 시간에 미치는 영향이 크게 달라지기 때문에,

시간 복잡도가 낮은 알고리즘을 선택하는 것이 중요합니다.

시간 복잡도를 이해하고 분석함으로써, 더 효율적인 알고리즘을 설계하고 구현할 수 있습니다.