[코드트리 조별과제] 3주차 레포트

이번 주차부터 자료구조, 알고리즘 코스를 따라가보려고 한다.

제일 먼저 시간복잡도 계산에 쓰이는 점근 표기법에 대해서 배웠다.

O는 가장 높은 차수 보다 같거나 높은 식을 뜻합니다.  Ω는 가장 높은 차수 보다 같거나 낮은 식을 뜻합니다. Θ는 최고차항(가장 높은 차수)을 뜻합니다.

 

위 개념을 바탕으로 시간 복잡도를 판단해보았다.

팁은,  시간복잡도는 일반적으로 최악을 기준으로 계산한다는 점이다.

 

관련해서 풀이한 문제 중 아래 문제가 어렵게 느껴졌다.

 

 

난 위 선지들 중에서 1번 선지와 4번 선지를 잘못 판단했다.

 

1번 선지의 경우 올바른 풀이는 다음과 같다.

N*N 크기의 배열의 모든 값을 한 번씩 순회하는 것은 N*N = N^2 개의 모든 인덱스를 참조하는 것이므로, 시간 복잡도는 O(N^2) 이 되어 옳은 선지이다.

 

4번 선지의 올바른 풀이는 다음과 같다.

4번은 틀렸는데, 반례를 들어보면 3N번 반복문이 수행되는 코드 역시 O(N) 의 시간복잡도를 갖게 되기 때문에 명확히 N배 더 느리다고 하기 어렵다는 걸 떠올릴 수 있다.

 

점근적 표기법이 아직은 추상적으로 와닿는다. 더 다양한 예제들을 보면서 익혀야겠다. 

특히 for 문 while문 등 반복문에서 시간 복잡도를 계산하는것이 까다롭다고 하는데 앞으로 배울 부분이라 기대가 된다.

수도코드를 읽으면서 시간복잡도를 계산하는 연습을 해야겠다.