시간복잡도/디버깅

시간복잡도

시간복잡도: 주어진 문제를 해결하기 위한 연산 횟수

 

시간 복잡도 유형

• 빅-오메가$( \Omega(n))$: 최선일 때(best case)의 연산 횟수
• 빅-세타$(\theta(n))$: 보통일 때(avarge case)의 연산 횟수
• 빅-오$(O(n))$: 최악일 때(worst case)의 연산 횟수

연산 횟수 계산 방법

• 연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

 

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외 ex) $ 3N $ → $ N $
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨 ex) $ N^2 + 10N $ → $ N^2 $

 

디버깅

디버깅(debugging): 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정

 

디버깅 방법

1. 코드에서 디버깅하고자 하는 줄에 중단점을 설정
2. IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행할 수 있으며, 이 과정에서 추적할 변수값도 지정할 수 있음
3. 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수 있음

 

참고: Do it 알고리즘 코딩테스트: 파이썬