[Algorithm] Time complexity (시간복잡도)

시간 복잡도는 알고리즘이 입력 데이터의 크기에 대해 얼마나 효율적으로 동작하는지를 나타내는 개념입니다.

좀 더 구체적으로는 알고리즘이 입력 크기에 따라 소요되는 계산 시간의 증가 정도를 표현합니다. 시간 복잡도는 알고리즘의 효율성을 분석하고 다른 알고리즘과 비교하는 데 사용됩니다.

 

프로그래밍에서 시간복잡도는 프로그래머가 작성한 코드의 Running time을 의미합니다. 

위 3줄 짜리 코드의 소요 시간은 7ns 입니다. 좋은 프로그램이라면 준수한 속도와 정확성이 뒷받침되어야 하기때문에 프로그램의 소요 시간이 중요하다고 말할 수 있습니다. 

그럼 반복문의 경우는 어떨까요?

• 'Outer loop'의 경우 5번  →  n번일 경우 n번
• 'Inner loop'의 경우 25번 →  n번일 경우 n^2번 

= 5n^2 + 3n 

 

이렇게 총 실행시간을 입력크기 n에 대한 함수로 표현한 결과를 시간복잡도라 합니다. 이때, n은 입력 데이터의 크기입니다. 복잡한 시간복잡도의 표현을 간단히 알아보기 위해서 함수의 최고차항으로만 시간복잡도를 표기한 것을 Big O 표기법이라고 합니다, 이는 상한을 나타내며 알고리즘의 실행 시간이 얼마나 빠르게 증가하는지를 나타냅니다.

 

 

예를 들어, O(n), O(n log n), O(n^2)은 각각 선형 시간, 로그 선형 시간, 이차 시간 복잡도를 나타냅니다. 이는 입력 크기 n이 커질 때 각각 선형적으로, 로그 선형적으로, 제곱적으로 증가한다는 것을 의미합니다.

 

시간 복잡도를 평가할 때는 최악 시간 복잡도, 평균 시간 복잡도, 최선 시간 복잡도 등 다양한 경우를 고려할 수 있습니다. 주로 최악 시간 복잡도가 가장 중요하게 다루어지며, 이는 최악의 상황에서도 알고리즘이 어느 정도의 성능을 보장하는지를 나타냅니다.

 

 

 

---

Time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. 

 

Big O Notation is a tool used to describe the time complexity of algorithms. It calculates the time taken to run an algorithm as the input grows.