시간복잡도

안녕하세요! 오늘은 시간 복잡도에 대해서 공부해볼까 합니다.

시간 복잡도란 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계(위키 백과)라고 하는데요 우리가 알고리즘도 수학과 컴퓨터 과학 그리고 언어학또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미합니다.(위키 백과)

컴퓨터 과학에서 알고리즘의 시간 복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것입니다. 알고리즘의 시간 복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 향을 제외시키는 방법입니다. 이런 방식으로 표현할 때, 예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대(어떤 n0보다 크지 않는 모든 n에 대하여) 5n^3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n^3)이라고 할 수 있습니다.

출처  (위키백과https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84)

오늘은 이렇게 시간 복잡도에 대해서 간단하게 알아보았고 앞으로 알고리즘 공부를 하실 때 알아두면 좋은 내용이니 참고 하시길 바랍니다.