StringBuilder를 사용하여 문자열 연결 최적화

Big O 표기법을 이해하고 있다고 가정합니다. 예제는 JavaScript에 있습니다. 정보 참고자료 Gayle Laakmann McDowell의 "코딩 인터뷰 크래킹"

많은 수의 문자열을 함께 연결하고 싶다고 상상해 보세요. 문자열의 길이가 모두 x이고 n개의 문자열이 있다고 가정하면 이 소요됩니다. $오(x+2x+\mathrm{.}\mathrm{.}\mathrm{.}+nx)$O(x+2x+...+nx) 시간. 각 연결에서 이전 문자열의 복사본을 만들고 새 문자열 위에 복사합니다. 따라서 첫 번째 반복에서는 x 문자를 복사해야 합니다. 다음 반복에서는 2x 문자를 복사해야 하는 등의 작업이 필요합니다.

앞서 설명한 런타임을 실제로 더 단순화할 수 있습니다.

$$x+2x+\mathrm{.}\mathrm{.}\mathrm{.}+nx=x(1+2+\mathrm{.}\mathrm{.}\mathrm{.}+n)=x(\frac{n(n-1)}{2})=x{n}^2$$x+2x+...+nx=x(1 +2+...+n)=x(2n(n−1)​)=xn2

따라서 이 문제에서 문자열을 연결하려면 다음이 필요합니다. $오(x{n}^2)$O(xn 2) 완료할 시간입니다. 물어보면 꽤 길어요. 알고리즘은 다음과 같습니다.

function joinWords(words) {
    let sentence = "";
    for (let w of words) {
        sentence = sentence + w;
    }
    return sentence;
}

StringBuilder 클래스

StringBuilder 클래스를 사용하면 이러한 긴 런타임을 방지할 수 있습니다. 간단히 말해서 이 클래스는 모든 문자열의 크기 조정 가능한 배열을 생성하고 필요한 경우에만 문자열에 다시 복사합니다.

JavaScript에서는 크기 조정 가능한 배열에 Join 메소드를 사용하여 문자열 목록을 문자열로 복사할 수 있습니다.

function joinWords(words) {
    let sentence = [];
    for (let w of words) {
        sentence.push(w);
    }

    return sentence.join("");
}

이제 배열에 문자열을 추가하면 $O(1)$O(1) 작업당 시간. 배열을 단일 문자열로 복사하는 마지막 단계는 다음과 같습니다. $O(n)$O(n) 여기서 n은 배열의 문자열 수입니다.

위 내용은 StringBuilder를 사용하여 문자열 연결 최적화의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!