1
C++에서 정렬 된 순서로 요소를 저장하는 std::set은 요소를 O (log n) 시간에 삽입 할 수 있습니다. 그러나 내가 아는 모든 방법은 선형 시간을 취합니다 :배열을 정렬 된 상태로 유지하기 위해 정렬 된 배열에 요소를 삽입하는 방법은 무엇입니까?
배열의 끝 부분에 요소를 삽입하고 이전 요소가 그보다 작을 때까지 이전 요소와 바꾸는 것은 선형 시간이 걸립니다.
배열에서 이진 검색을 사용하고 삽입 할 요소의 위치를 찾는 경우 O (log n) 시간이 소요되지만 요소를 주어진 위치에 삽입하는 것은 최악의 경우 O (n) 시간이 걸립니다.
정렬 된 배열을 힙으로 사용하면 O (log n) 시간에 요소를 삽입 할 수 있지만 배열이 그 이후에 힙을 유지하더라도 정렬 된 것으로 보장 할 수는 없습니다.
O (log n) 시간에 정렬 된 배열에 요소를 삽입하는 방법이 필요하며 std::set이이를 수행 할 수 있기 때문에이 방법이 가능하다는 것을 알았지 만 그 방법은 알지 못합니다.
std :: set의 소스를 살펴 보셨습니까? –
std :: set은 항상 내부적으로 정렬되며 요소를 삽입하는 올바른 방법은 삽입 함수를 사용하는 것입니다. See [link] (http://www.cplusplus.com/reference/set/set/) – lindell
@lindell std :: set는 C++에서만 사용할 수 있지만 C에서는 사용할 수없는 알고리즘을 찾고 있습니다. 프로그래밍 언어가 무엇이든간에 – 2147483647