자바에서 toCharArray() 및 toString()의 런타임은 무엇입니까?

Question

이러한 성능은 무엇입니까?

BigInteger -> toString() // what is the runtime? 

String -> toCharArray() // what is the runtime? 

감사합니다.

Answer 1

BigInteger을 문자열로 변환하는 것은 O(N^2)입니다. 여기에서 N은 결과의 자릿수입니다. 내부 표현의 기준으로 대상 기본을 나눌 수 없습니다. 대상베이스가 스토리지베이스로 나눌 수있는 경우 변환은 O(N)입니다.

내부 표현이 기본 256 인 경우 기본 10으로 변환하는 것을 고려하십시오. 십분의 일 나누기가 발생했습니다 N 번; 매번 BigInteger 표현의 모든 요소가 수정됩니다. 표현의 요소 수는 인쇄물의 자릿수에 비례하므로 전체 변환에는 O(N^2)이 필요합니다.

반면에, 기본 256 내부 표현에서 큰 int의 16 진수로 변환하려면 O(N)이 필요합니다.이 경우에는 나누기가 필요하지 않기 때문입니다. 각 하위 요소는 나머지 요소와 분리하여 변환 할 수 있으며 하위 요소의 수는 출력물의 자릿수에 비례합니다.

String.toCharArray()까지는 O(N)입니다. 여기에서 N은 문자열의 문자 수입니다. 각 문자를 출력에 복사해야하기 때문입니다.

Answer 2

toString() 메서드는 System.arrayCopy를 사용하여 구현되며이 메서드는 기본 메서드입니다.

public char[] toCharArray() { 
    char result[] = new char[count]; 
    getChars(0, count, result, 0); 
    return result; 
} 

public void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) { 
    // bounds checking 
    System.arraycopy(value, offset + srcBegin, dst, dstBegin, 
     srcEnd - srcBegin); 
} 

나는 기본 방법은 아마도 O (N) 인 후드 방어 적이기를 사용하는 상상, 그래서 런타임 O는 실제 JVM 구현에 따라 달라집니다. 이 원시 메소드의 소스를 확인하려면 open jdk 소스를 살펴보십시오.