[TIL] 자바 알고리즘 코딩 테스트 : 시간 복잡도 / 디버깅

 

알고리즘에서의 시간 복잡도

주어진 문제를 해결하기 위한 연산 횟수 (일반적으로 1억 번의 연산을 1초의 시간으로 간주)

 

• 빅-오메가 : 최선 ex) 1번
• 빅-세타 : 보통 ex) n/2번
• 빅-오 : 최악 ex) n번 -> 항상 최악의 케이스 염두 해둘 것

 

연산 횟수 계산  = 알고리즘 시간 복잡도 X 데이터의 크기 

-> 위의 공식을 대입해 해당 알고리즘이 문제에 적합한지 판단함

-> 시간 복잡도 도출시 상수는 계산에서 제외 ex) 3N -> N

-> 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨

---

 

디버깅

문법 오류나 논리 오류를 찾아 바로잡는 과정

 

1) 변수 초기화 오류 Variables탭

2) 반복문 인덱스 범위 지정 오류 ex) i<N, i<=N, i<N-1

3) 잘못된 변수 사용 오류

4) 자료형 범위 오류 ex) int -> long형으로 선언하자