시간복잡도

[알고리즘] 시간복잡도 구하기

처음 알고리즘 분류 글을 작성하게 되었습니다(두근) 작년(2022) 이맘때쯤 학교에서 학습했던 알고리즘의 시간복잡도에 관한 내용입니다. 코딩테스트가 익숙해지면서 효율성을 요구하는 문제들과 맞딱뜨리게 되었는데, 이때 알아야 할 기초 개념이 바로 시간복잡도입니다. 내가 짠 코드가 입력 대비 얼마큼의 시간이 필요한가를 계산하여 효율성을 판단하고, 비효율적이라면 어떤 부분을 수정할지 생각해 볼 수 있기 때문입니다. 목차 1. 정의 & 표기법 2. O(1) 2. O(N) 3. O(N²) 4. O(NlogN) 1. 정의 & 표기법 위키 백과에서 인용해 온 컴퓨터과학에서 시간복잡도의 정의 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것 다음은 시간복잡도의 3가지 표현법입니다. 최..