파이썬혹은 C++에서 리스트를 사용하다 중간에 있는 요소를
삭제하면 뒤에 요소들이 앞으로 밀리면서 O(N)이 소요됩니다.
이런 연산을 여러번 하면 O(N^2)이 되어 부담스러워 집니다.
O(N)미만으로 요소를 삭제할 수 있나요?
단, 이분 탐색을 사용하기 위해 연결리스트는 사용할수 없고,
정렬된 순서는 항상 유지해야 합니다(뒤의 요소와 바꿔서 삭제할수 없음).
C++에서 std::list의 중간 요소 삭제의 시간복잡도는 O(1) 입니다.
말씀하신 것은 임의의 원소에 접근하는 것을 포함하는 것 같은데, 이 지우는 것과 임의 원소 접근, 이 두 가지는 분리해서 이야기 되어야할듯 합니다.
Ropes: an Alternative to Strings
감사합니다. 해결되었습니다.
댓글을 작성하려면 로그인해야 합니다.
kkmandoo09 1년 전
파이썬혹은 C++에서 리스트를 사용하다 중간에 있는 요소를
삭제하면 뒤에 요소들이 앞으로 밀리면서 O(N)이 소요됩니다.
이런 연산을 여러번 하면 O(N^2)이 되어 부담스러워 집니다.
O(N)미만으로 요소를 삭제할 수 있나요?
단, 이분 탐색을 사용하기 위해 연결리스트는 사용할수 없고,
정렬된 순서는 항상 유지해야 합니다(뒤의 요소와 바꿔서 삭제할수 없음).