kkmandoo09   1년 전

파이썬혹은 C++에서 리스트를 사용하다 중간에 있는 요소를

삭제하면 뒤에 요소들이 앞으로 밀리면서 O(N)이 소요됩니다.

이런 연산을 여러번 하면 O(N^2)이 되어 부담스러워 집니다.

O(N)미만으로 요소를 삭제할 수 있나요? 

단, 이분 탐색을 사용하기 위해 연결리스트는 사용할수 없고, 

정렬된 순서는 항상 유지해야 합니다(뒤의 요소와 바꿔서 삭제할수 없음).

readiz   1년 전

C++에서 std::list의 중간 요소 삭제의 시간복잡도는 O(1) 입니다.

말씀하신 것은 임의의 원소에 접근하는 것을 포함하는 것 같은데, 이 지우는 것과 임의 원소 접근, 이 두 가지는 분리해서 이야기 되어야할듯 합니다.

kkmandoo09   1년 전

감사합니다. 해결되었습니다.

댓글을 작성하려면 로그인해야 합니다.