이 함수의 계산 복잡도는 얼마입니까?

이 함수의 계산상의 복잡성이 무엇인지 궁금합니다.이 함수의 계산 복잡도는 얼마입니까?

2^(로그 (n)은 -1)

로그 그것은 모든 대수 및 능력을 산출하여 어떤 알고리즘에 따라 기재 2.

2012-09-04 dgamma3

당신은 이미 답을 가지고 있습니다. O (2^logn)이다. 이것은 지수 함수입니다. – DarthVader

@DarthVader 아니요. OP는이 기능 자체의 참조를 요구합니다. –

@DarthVader 아, 숫자가 기본 숫자가되는 대수로 키우는 경우 지수가 아니라 선형입니다. –

이다. 이 함수가 본질적으로 2로 나누어지는 것을 알아 차릴만큼 똑똑하다면, 오른쪽 시프트를 수행하여 정수에 대해이를 일정 시간 (즉, O(1))으로 구현할 수 있습니다.

2012-09-04 05:21:39

감사합니다. 그래서 숫자가 2로 나눌 수 있기 때문에, 그것을 어떻게 만들지 O (1) – dgamma3

예, 이것은 이상한 질문입니다. 일종의 질문입니다.이 함수의 복잡성은 무엇입니까? Sort(). :) – aquinas

@ dgamma3 답변을주의 깊게 읽으십시오. (그리고 2로 나눌 필요가 없다). –

답변