메모리와 관련하여 아래 코드의 복잡성은 무엇입니까?

Question

나는 빅 핸드 (Big-O) 표기법을 here에서 읽었으며 복잡도 계산에 관한 질문이 거의 없었습니다. 아래의 코드에서 복잡성을 계산했습니다. 귀하의 의견을 동일하게 받아야합니다.

private void reverse(String strToRevers) 
    { 
     if(strToRevers.length() == 0) 
     { 
      return ; 
     } 
     else 
     { 
      reverse(strToRevers.substring(1)); 
      System.out.print(strToRevers.charAt(0)); 
     } 
    } 

메모리 요소를 고려하면 위의 코드는 n 문자의 문자열에 대해 복잡성이 O (n^2)입니다. 설명은 n 문자로 구성된 문자열에 대한 것입니다. 아래 함수는 n-1 회 반복적으로 호출되며 각 함수 호출은 단일 문자 (stringToReverse.charAT (0)) 문자열을 만듭니다. 따라서 그것은 n * (n-1) * 2이며 이는 o (n^2)로 변환됩니다. 이게 맞는지 알려주시겠습니까?

Answer 1

따라서 n (n-1) * 2는 o (n^2)로 변환됩니다. 이게 맞는지 알려주시겠습니까?

거의 :이 아니라 *2이며 O (n^2)입니다. o (n^2) (little-O) means something else이므로 구분이 중요합니다.

이것은 우리가 이것을 의사 코드로 간주한다고 가정합니다. 언어 별 구현 및 스마트 컴파일러는 실행 시간을 크게 향상시킬 수 있습니다. 예를 들어, 단순히 문자열을 뒤집어 쓴다는 것을 관찰 할 수있는 컴파일러는 O (n) 인 내부 반전을 수행 할 수 있습니다.

Answer 2

자바처럼 보이므로 이 아니며 O (n ** 2)입니다. 문자열은 기본 문자 시퀀스 버퍼를 공유하기 때문입니다. 그들은 불변의 객체이기 때문에 이것을 할 수 있습니다.

하지만 스택 공간에서는 O (n)입니다. 그 좋지 않다. 가변적 인 문자 작업 버퍼를 할당하고 문자열을 역으로 변환 한 다음 전체를 한꺼번에 인쇄하는 것이 좋습니다.