dla5420   2년 전

* 전반적으로 틀리진 않지만 너무 구체적으로 설명하는걸 싫어하는 타입입니다.


MenOfPassion(A[], n) {

i = ⌊n / 2⌋;

return A[i]; # 코드1

}

생긴게 이상해서 그렇지 매우 간단합니다.

입력 받은 값을 n으로 저장하고 함수를 수행하게 됩니다.

수행 내용은 간단하게도 i = n//2 입니다

return A[i] 부분은 항상 한번만 수행하게 됩니다. (나누기 동작 엔딩 파트)

따라서 시간 복잡도는 O(1) 입니다.

O(1) 이란 입력 값에 상관 없이 항상 일정 시간 내에 결과를 낸다는 뜻입니다.

그럴 수 밖에 없는게 단순 나누기니깐요.

나누기도 한번만 실행 됩니다.

여러번 나눌 필요가 없는 단순 나누기 코드입니다.

이걸 다항식으로 나타내기에는 O(1) 이다보니

T(n) = C, C는 상수 값 입니다.

상수라는 뜻은, 제곱이 하나도 없는 자연수로 끝나는 방정식이 됩니다.

따라서 최고 차항의 지수는 0이 됩니다.

문제에서는 최고차항이 3이면 4를 출력하라는데

상수 값을 가지기에 n^2 뿐만 아니라 그 이상으로 모든 차항이 0의 지수를 가지기에

0으로 동일합니다. 낚시 문항이라 생각합니다.

이 문제는 코딩 능력을 보기 보다는

알고리즘 분야의 시간복잡도 확인 문제여서

코딩만 할줄 아는 사람은 풀 수 없는 문제가 되겠네요.

geniusyeon   1년 전

아 그렇군요! 재귀함수처럼 여러번 실행되는 줄 알고 고민하고 있었네요.

댓글을 작성하려면 로그인해야 합니다.