재귀 함수에 대해 읽었으며이 수학 공식을 알아 내려고 노력했습니다. 아마도 대수 함수라고 생각 했겠지 만 그럴 것 같지 않습니다. 누군가가 올바른 방향으로 나를 가리킬 수 있다면, 나는 그것을 감사하겠습니다.이 재귀 함수가 무엇을 반환하는지 확실하지 않음
unsigned f(unsigned n){
if(n<2)
return 1;
return 1 + f(n/2);
}
이 기능에 도달 할 때까지 함수가 2 전체 수를 나누어 실행 횟수를 반환 제로
EX : 당신은 수학 공식에 대한 우려 때문에
f(8)-
return f(4) //continue on
return f(2) //continue on
return f(1) //we know this is 1
return f(2) //now we can do this one, 2
return f(4) //and this one, 3
그 함수는 다음을 기반으로합니다.
여기에 있습니다 : f은 n :
f(n) = 1 + f(n/2) if n >=2
f(n) = 1 if n <=1 //n is unsigned so n >=0
위의 공식을 염두에두고 기본 알고리즘은 로그 복잡성을 갖습니다. 그 이유는 모든 단계에서 n의 크기를 반으로 줄이며 log(n) (기본 2) 단계가 1에 도달하기 때 문에 O(logn)의 로그 복잡성 때문입니다.
구현한다.
내가 당신이 말한 "수학 함수"알고 그 기존 답변에 대한 관점을 설정,하지만 다른 관점을 보여주기 위해, 그것은 반환 : 당신이 1 비트 필요하다고하면 (n를 저장하는 데 필요한 비트의
n|1 설정된 최상위 비트의n)때로는 코드를 볼 때 기능이 다른 의도로 사용될 수 있음을 알 수 있습니다. 원근법으로 인해 사용 컨텍스트를 더 쉽게 이해할 수 있습니다.
대수 함수가되는 기능은 복잡성과 관련이 없으며 그 반대도 마찬가지입니다. –
@MooingDuck 함수가 대수 함수라는 것을 언급하지는 않았습니다. 함수가 구현하는 알고리즘은 로그의 복잡성을가집니다. – taocp
그게 바로 내가 downvoted 이유입니다. –