시간복잡도와 빅오 O(N^2)는 나쁘고 O(NlogN)는 괜찮고 O(N)는 좋다
빅오표기법 빅오 표기법(Big O notation)은 알고리즘의 성능 분석을 위한 수학적인 표기법이다. 컴퓨터가 같은 계산결과를 내더라도 어떤 자료구조와 어떤 알고리즘을 사용하는가에 따라 계산시간이 달라진다.피보나치 수열을 구하는 알고리즘을 보자. 두개의 알고리즘의 실행시간은 계산횟수를 통해 유추해볼 수 있다. if문의 경우 시간복잡도도 O(1)이고 덧셈의 시간복잡도도 O(1)여서 함수한번 호출하는데에는 시간복잡도가 O(1)지만 함수 호출 횟수가 많아질 경우 프로그램 실행속도가 급격하게 느려진다. 하지만 cache라는 리스트를 도입해서 값을 임시저장해놓으면 계산횟수가 획기적으로 줄어든다. 일반적으로 코딩테스트의 실행시간 제한은 1~2초이고 1억까지는 1~2초안에 실행된다고 한다. 오른쪽의 경우 30번째 ..
프로그래밍/코딩테스트준비
2023. 5. 8. 11:23
