공간 복잡성 O (1) 문자열 저장

Question

공간의 복잡성에 다소 혼란 스럽습니다. 이 O (1) 공간 복잡성 또는 O (N) 복잡성입니까? 크기가 n 인 문자열을 생성하기 때문에 공간의 복잡성은 O (N)가 맞습니까?

## this function takes in a string and returns the string 

def test(stringval): 
stringval2 = "" 
for x in stringval: 
    stringval2 = stringval2 + x 
return stringval2 

test("hello")} 

Answer 1

네, 맞습니다. 각 개별 문자가 어딘가에 저장되어야하기 때문에 길이가 n 인 새로운 문자열을 저장하는 공간의 복잡도는 Θ (n)입니다. 원칙적으로 stringval2이 stringval1의 복사본이되고 잠재적으로 copy-on-write 또는 기타 최적화를 사용한다는 것을 알면 공간 사용을 줄일 수 있지만이 경우에는 의심 할 여지가 없습니다.

희망이 도움이됩니다.