[python] 반복 문자열의 시간 복잡성이 실제로 O (n ^ 2) 또는 O (n)을 추가합니까?

Program / 글쓴이

CTCI에서 문제를 해결하고 있습니다.

1 장의 세 번째 문제는 다음과 같은 문자열을 사용하는 것입니다.

'Mr John Smith '

중간 공간을 %20다음 으로 대체하도록 요청합니다 .

'Mr%20John%20Smith'

저자는이 솔루션을 Python으로 제공하며 O (n)이라고합니다.

def urlify(string, length):
    '''function replaces single spaces with %20 and removes trailing spaces'''
    counter = 0
    output = ''
    for char in string:
        counter += 1
        if counter > length:
            return output
        elif char == ' ':
            output = output + '%20'
        elif char != ' ':
            output = output + char
    return output

내 질문:

나는 이것이 왼쪽에서 오른쪽으로 실제 문자열을 스캔하는 측면에서 O (n)임을 이해합니다. 하지만 파이썬의 문자열은 불변하지 않습니까? 문자열이 있고 +연산자를 사용하여 다른 문자열을 추가 하면 필요한 공간을 할당하고 원본을 복사 한 다음 추가 문자열을 복사하지 않습니까?

n길이가 각각 1 인 문자열 모음이 있으면 다음을 수행합니다.

1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2

또는 O (n ^ 2) 시간 , 그래? 아니면 파이썬이 추가를 처리하는 방법이 잘못 되었습니까?

또는 낚시하는 법을 가르쳐 주실 수 있다면 어떻게해야합니까? 나는 구글을 공식 소스로 시도하는데 실패했다. https://wiki.python.org/moin/TimeComplexity를 찾았 지만 문자열에 아무것도 없습니다.

답변

Python의 표준 구현 인 CPython에는이를 일반적으로 O (n)으로 만드는 구현 세부 사항이 있으며 , 바이트 코드 평가 루프가 호출 +하거나 +=두 개의 문자열 피연산자 를 사용 하여 코드에서 구현됩니다 . 파이썬이 왼쪽 인수에 다른 참조가 없음을 감지 realloc하면 문자열의 크기를 조정하여 복사를 방지하도록 호출 합니다. 이것은 구현 세부 사항이므로 realloc문자열을 자주 이동해야하는 경우 성능이 어쨌든 O (n ^ 2)로 저하 되기 때문에 의존해서는 안됩니다 .

이상한 구현 세부 사항이 없으면 알고리즘은 2 차 복사 양으로 인해 O (n ^ 2)입니다. 이와 같은 코드는 C ++와 같이 변경 가능한 문자열이있는 언어에서만 의미가 있으며 C ++에서도 사용하려는 +=.

답변

작성자는 여기에있는 최적화에 의존하지만 명시 적으로 신뢰할 수는 없습니다. strA = strB + strC일반적으로 O(n)기능을 만드는 것 O(n^2)입니다. 그러나 전체 프로세스가 O(n)이고 배열을 사용 하는지 확인하는 것은 매우 쉽습니다 .

output = []
    # ... loop thing
    output.append('%20')
    # ...
    output.append(char)
# ...
return ''.join(output)

요컨대, append작업은 분할 O(1) 되어 ( O(1)배열을 올바른 크기로 미리 할당하여 강력하게 만들 수 있지만 ) 루프를 O(n)만듭니다.

그리고 join는 또한 O(n)이지만 루프 외부에 있기 때문에 괜찮습니다.

답변

Python Speed> 최고의 알고리즘과 가장 빠른 도구 사용 에서이 텍스트 스 니펫을 찾았습니다 .

문자열 연결은 가장으로 수행 ''.join(seq)하는이다 O(n)과정. 반대로 '+'또는 '+='연산자를 사용하면 O(n^2)각 중간 단계에 대해 새 문자열이 작성 될 수 있으므로 프로세스 가 발생할 수 있습니다. CPython 2.4 인터프리터는이 문제를 다소 완화합니다. 그러나 ''.join(seq)모범 사례로 남아 있습니다.

답변

미래 방문자를 위해 : CTCI 질문이므로 여기에서는 특히 OP 및 책에 따라 urllib 패키지 학습에 대한 참조가 필요하지 않습니다.이 질문은 배열 및 문자열에 관한 것입니다.

@ njzk2의 의사에서 영감을 얻은 더 완전한 솔루션은 다음과 같습니다. 

text = 'Mr John Smith'#13 
special_str = '%20'
def URLify(text, text_len, special_str):
    url = []
    for i in range(text_len): # O(n)
        if text[i] == ' ': # n-s
            url.append(special_str) # append() is O(1)
        else:
            url.append(text[i]) # O(1)

    print(url)
    return ''.join(url) #O(n)


print(URLify(text, 13, '%20'))

답변