[알고리즘] 시간복잡도

시간복잡도
입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정된다.
어떠한 알고리즘이 주어진 입력크기를 기반으로 어떠한 로직이 몇번 반복되었는가를 중점으로 설명한다.

 

 

 

시간복잡도가 필요한이유
효율적인 코드로 개선하는데 쓰이는 기준이 된다. (성능향상)

 

 

빅오표기법
복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법이다.

 

상수시간 시간복잡도 O(1)
상수시간 시간복잡도는 입력크기와 상관없이 일정한 시간복잡도를 가지는 것을 말하며 O(1)의 시간복잡도를 쓴다.
ex) cin, cout, scanf, printf, 곱하기, 나누기, 나머지연산, 빼기, 간단한비교if문, 배열의 인덱스참조,