다음 메소드의 시간 복잡도

Question

다음 메소드의 시간 복잡성을 판별하려고합니다. 처음에는 m^3을 얻을 수있는 for 루프가 3 개 있습니다. 어떻게 끝낼 지 재귀 호출의 시간 복잡도를 결정하는 방법을 모르겠습니다.

누군가가 도와 줄 수 있습니까?

void p(int n, int m) { 
    int i,j,k ; 
    if (n > 0) { 
     for (i=0 ; i < m ; i++) 
      for (j=0 ; j < m ; j++) 
       for (k=0 ; k < m ; k++) 
        System.out.println(i+j*k) ; 
     p(n/m, m) ; 
    } 
} 

Answer 1

O (m^3)은 앞에서 언급 한 것처럼 임의의 재 등장없이 실행됩니다.

총 시간은이 단일 단계 시간의 배수에 불과합니다.

n = m^(k-1)은 k 번 실행 된 단계이므로 O (ln (n) * m^3) 인 O (k * m^3)를가집니다.

: 단계 Followinyg

Answer 2

아래는 공식적인 방식으로 시간 복잡도를 추론 할 수있는 것