[자료구조] 시간복잡도 Time Complexity

(1) 시간복잡도 Time Complexity

프로그램의 연산 시간과 입력의 함수 관계를 의미하며,

특정 알고리즘 로직의 수행시간을 시간복잡도라고 할 수 있습니다.

일반적으로 시간복잡도는 빅오 표기법으로 표현합니다.

우리는 시간복잡도를 기준으로 알고리즘을 평가할 수도 있고,

이를 통해서 로직을 개선하고 알고리즘을 최적화할 수도 있습니다.

속도는 SW 성능을 평가하는 중요한 지표이니, 시간복잡도가 중요하게 여겨질 수 밖에 없겠죠?

(2) 빅오 표기법 Big-O Notation

빅오 표기법은 input "N"으로 입력을 표현할 때, 해당 로직을 함수로 나타낸 낸 수식입니다.

이때 최고차항만 표기하고 상수항은 생략하여 표기합니다.

그렇기 때문에 입력값 N에 대한 개략적인 수행시간만 알 수 있고, 정확한 시간을 알기는 어렵습니다.

특정 알고리즘의 시간복잡도를 확인 할 때는 최악의 경우, 그리고 최선의 경우의 시간복잡도를 모두 확인해야합니다.