시간복잡도(Time Complexity)

알고리즘의 시간복잡도

우리는 살면서 어떤 목적지로 이동할 때 대부분 최단거리를 찾아서 이동을 합니다.

프로그래밍에서도 시간복잡도가 가장 낮은 알고리즘을 채택하여 실행시간을 단축하려고 노력합니다.

 

시간 복잡도는 알고리즘의 수행 시간을 나타내는 측정 방법입니다.

특정 입력 크기에 대한 알고리즘의 수행 시간을 분석하여, 알고리즘의 효율성을 판단하는 데 사용됩니다.

보통 "O(n)" 표기법을 사용하여 표시하며, n은 입력 크기를 나타냅니다.

 

예를 들어, 

 

O(1) - 상수 시간 복잡성: 입력 크기에 관계없이 항상 동일한 시간이 걸리는 알고리즘입니다. (예: 인덱스를 사용하여 배열에서 요소 검색)

O(n) - 선형 시간 복잡성: 입력 크기에 따라 실행 시간이 선형으로 증가하는 알고리즘입니다. (예: 배열의 선형 검색)

O(n^2) - 2차 시간 복잡성: 실행 시간이 입력 크기의 제곱에 비례하는 알고리즘입니다. (예: 버블 정렬 알고리즘)

O(log n) - 로그 시간 복잡성: 입력 크기에 따라 실행 시간이 로그로 증가하는 알고리즘입니다. (예: 이진 검색 알고리즘)

 

 

시간 복잡성은 알고리즘의 실행 시간에 대한 추정치만 제공하고 사용된 특정 구현 및 하드웨어에 의존한다는 점에 유의해야 합니다.

 

 

 

 

참고: https://dingrr.com/blog/