재귀 함수의 시간 복잡도를 계산하는 방법은 무엇입니까?

Question

다음 코드의 복잡도는 얼마나됩니까?

는

내 생각 엔 : 루프

즉 일정 시간 동안 3. 실행 기능은 N/3 자체를 호출합니다. 따라서 'n'은 매회 3 번 축소되고 시간 복잡도는 O (로그 N)입니까?

void function(int n){ 
    if(n == 1) 
     return 1; 
    for(int i = 0; i < 3; i++){ 
     cout << "Hello"; 
    } 
    function(n/3); 
} 

Answer 1

예, 그것의 O (N 로그). C가 나타납니다 횟수가 1에 도달하기 전에 3에서 N을 나눌 수있는 횟수 될 것

f(n) = C + f(n/3) = C + C + f(n/9) = C + ... + C + f(1)

: 처음 몇 전화가 갈 것입니다 루프 C.에 의해 수행 작업의 양을 전화 , 이는 정확하게 로그입니다. n. 따라서 전체 작업은 C * log n이거나 O (로그 N)입니다.