공간 복잡성 반복

Question

그래서 두 부분으로 나뉩니다.

나는 시간 복잡도를 요청 몇 가지 코드를 가지고 있고, 그것은 (중첩) 루프 3으로 구성

public void use_space(int n) 

    for(int i=0;i<N;i++) 
    for(int j=0;j<N;j++) 
    for(int k=0;k<N;k++) 

//and at the end of the code, it makes a recursive call to the function 
use_space(n/2); 
use_space(n/2); 

을 내가했다이 시간 복잡도 재발 파생 그래서 : T(n) = 2T(n/2) + n^3. 그 이유는 각각 n/2 시간으로 구성된 함수에 대한 2 회 재귀 호출이 있었고 중첩 된 for 루프는 n^3 (3 루프) 시간이 걸리기 때문입니다.

이 맞습니까?

그리고 공간의 복잡성에 대한

, 나는 S(n) = S(n/2) + n

희망 누군가가 명확히하고이 잘못된 경우 설명/말해 줄 수 있어요. 모든 도움을 주시면 감사하겠습니다.

Answer 1

귀하의 시간 복잡성이 정확합니다. masters theorem을 사용하여 간단하게 만들 수 있습니다. Theta(n^3)

그러나 공간 복잡성은 약간 잘못된 것처럼 보입니다.
use_space(n)의 모든 호출에 대해 i, j 및 k의 세 숫자를 저장해야합니다. 이 숫자는 대부분 n 크기입니다 (n == N 인 경우 혼합 한 것 같습니다). 따라서 log n 비트를 저장해야합니다. use_space을 완료 한 후에 공간을 비우기 때문에 추가 전화 use_space(n/2) 만 저장하면됩니다.

그래서 공간 복잡성은 S(n) = S(n/2) + 3 log n이됩니다.

개선 : 당신은 세 개의 루프를 종료 한 후 i, j 및 k을 확보 할 수 있으므로 (동시에) 3 log n 및 S(n/2) 필요하지 않지만 처음 3 log n이 S(n/2) 후가 될 것이다 프리스트 3 log (n/2) 다음 S(n/4) (등등)이므로 동시에 사용되는 최대 공간 만 필요합니다 (3 log n).