0
String과 같은 특정 유형의 매개 변수를 사용하는 함수를 작성하고 다른 데이터 구조의 경우 훨씬 쉽게 처리 할 수있는 방식으로 조작해야하는 경우가 종종 있습니다. 문자열을 문자 배열로 변환하고 O (1) 공간을 차지하는 함수를 고려하면서 String을 null로 설정할 수 있습니까? 아니면 다른 복사본을 즉시 삭제하더라도 모든 요소를 복사하면 O (N)이됩니까? 문자열은 불변이므로 예제로 사용합니다. 또 다른 경우에는, 다른 구조체에 추가 할 때 한 구조체의 데이터를 삭제하려고합니다.데이터 구조와 공간 복잡성 복사하기
여기서 예제로 String과 char []를 사용하고 있습니다. 일반적으로 다른 사본을 삭제하더라도 데이터를 복사하면 알고리즘의 공간 복잡성을 줄일 수 있는지 알고 싶습니다.
내가 다른 구조를 만들 때 한 구조에서 삭제할 수만 있다면 내 함수가 O (1) 공간 만 필요하다고 생각합니까? 스택에서 삭제하는 동안 내가 arraylist에 추가 할 수있는 것처럼? – user137717
@ user137717 arraylist에 대한 일정한 크기의 버퍼를 가지고 있다고 가정하면 맞습니다. (현재 크기의 몇 퍼센트 버퍼와 대조적으로) –
@ user137717 그 주석을 수정해야합니다 - arraylist가 크기가 조정될 때 일반적으로 다른 복사본을 수행해야합니다 (예 : arraylist 크기가 n이고, 새로운 arraylist 크기로 n + 10을 할당하고 이전 배열을 새 배열에 복사 한 다음 이전 배열을 할당 해제해야 함). 그 사본에는 선형 공간이 필요하다는 것. 일정한 공간을 요구하기 위해서는 청크 분할리스트 (배열의 링크리스트)와 같은 것으로 복사 할 필요가 있습니다. C와 같은 언어는'realloc'을 사용하여 in-place 배열의 크기를 조절할 수 있습니다 (그러나 이것은'realloc' 구현에 달려 있습니다) –