정렬된 상태로 유지하면서 삽입 vs 일단 뒤에다가 삽입후 정렬

[익명(211.215)]

최종 결과는 정렬된 상태의 list여야됨

예를들어

1 5 6 7 20 30 이렇게 정렬된 상태의 list에 13이라는 data를 삽입한다고 치자.

첫번째 방법은 binary search를 통해서 6 < 13, 20 <13, 7 <13 -> 7뒤에다가 13을 삽입하는방법이고

두번쨰 방법은 일단 1 5 6 7 20 30 13을 해놓고 이거를 정렬해서 1 5 6 7 13 20 30을 얻는건데

당연히 첫번째가 더 빠르겟지?

[_FL(121.165)]

알고리즘 구현에 따라 다르겠지요

[익명(163.44)]

후자

[익명(163.44)]

첫번째는 넣을때마다 서치해야되고 후자는 막판에 한번 정렬하면됨

[익명(163.44)]

1회실행이면 뭐비슷할거같은데

[익명(211.215)]

한번만 실행임

[익명(211.215)]

binary search는 logn,퀵소트나 merge소트 쓰면 nlogn이라서 1번실행이라 치면 첫번째 방법이 더 괜춘한거 아니에요?

[휘발성(reduxx)]

list에서 binary search..? - 164260의 휘발성 계정

[휘발성(reduxx)]

한번만 실행이라는게 뭔뜻인지 잘 모르겠는데 원소 하나 추가하는거면 당연 전자가 빠르긴 하겠는데 - 164260의 휘발성 계정

[휘발성(reduxx)]

원소 n개 추가한다 치면 빅오는 똑같이 찍히겠지만 구현상 후자가 빠를거같네요 - 164260의 휘발성 계정

[익명(211.215)]

애초에 list대신 bst를 쓰는게 나을려나요 그럼?

[익명(211.215)]

뭐 그러면 정렬하는게 의미가 없어지긴 하겟지만