[일반] 저 밑에 학교 슬라이드에 있는 insert 코드인데

[수학최종보스(finalbossmath)]

여기선 내가 입력한 POS(위치) 까지

head부터 출발해서 하나하나씩 다음 node 의 주소를 옮기는 과정이 적혀있음

while에 있네 .

물론 STL에 있는 insert랑 똑같은 코드는 아니고 doubly linked list를 설명하자고 교수님이 쓴건데

교수님이 거의 비슷하다고 하는데.

그리고 내 동기도 실행했는데 O(n)나온다고 했는데 

[익명(1.240)]

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf
904페이지
Complexity:
Insertion of a single element into a list takes constant time and ... (생략)

[익명(1.240)]

교수 말이 C++ 표준화 기구에서 내놓은 공식 명세보다 위에 있을 수는 없음

[익명(1.240)]

같은 결과를 내고 싶다면 원소를 찾는 과정까지 측정에 포함해야 같아짐

[수학최종보스(finalbossmath)]

이렇게 써져 있는데

[수학최종보스(finalbossmath)]

The time complexity of inserting a single element into a list depends on where the element is being inserted and what type of list data structure is being used. For a typical list data structure like an array-based list or a linked list: Insertion at the end (appending): O(1) - This is constant time because you are simply adding the element at the end of the list, and no shifting or rearranging

[수학최종보스(finalbossmath)]

Insertion at a specific index: O(n) - Similar to insertion at the beginning, if you're inserting an element at a specific index, you may need to shift elements to make room for the new element, which again requires iterating through the list and moving elements.

[수학최종보스(finalbossmath)]

인터넷에 다 찾아봐도 O(n)이라고 나와있는데 저기서는 O(1)으로 나와있네 뭐지??

[익명(1.240)]

몇페이지인지좀

[수학최종보스(finalbossmath)]

https://www.hackerearth.com/practice/notes/standard-template-library/

[수학최종보스(finalbossmath)]

여기서도 index로는 O(n)이라고 하던데
https://medium.com/@rodrigues.b.nelson/choosing-wisely-c-containers-and-big-oh-complexity-64f9bd1e7e4c

[수학최종보스(finalbossmath)]

저 사람들 다 착각한거였노

[익명(1.240)]

with iterator: O(1)은 안보임? 너가 한 일이 이거임 이터레이터부터 받아 온 다음 삽입하기

[수학최종보스(finalbossmath)]

insert( ): It insert new elements in the list before the element on the specified position. Its time complexity is O(N). 라는ㄷ

[수학최종보스(finalbossmath)]

애초에 insert가 포지션이 iterator밖에 안받는데???

[익명(1.240)]

여기까지만 말하고 더 이상은 덧붙이지 않겠음 C++ 공식 draft나, 그걸 받아적은 cppreference나 constant time이라고 말하고 있는데, 교수나 블로그들이 선형시간이라고 말한다고 그게 설득력 있진 않다고 생각됨. 그리고 linked list를 굳이 써야 할 이유는 삽입때문임, 캐시히트도 안되고 삽입 제외하면 모든 면에서 벡터보다 덜떨어진 자료구조를 STL에 넣을 이유는 없음. 그리고 n번째 위치에 m개의 원소를 삽입하는 연산을 생각했을 때, O(nm)의 구현이 맞을지, O(m)의 구현이 맞을지 생각해보기 바람

[익명(1.240)]

모든건 현실적인 이유에서 선형시간이라고 말하는것 뿐이고, 이론상으로는 상수시간이 맞음.

[수학최종보스(finalbossmath)]

근데 궁금한게 애초에 C++에서 insert가 iterator만 받지 index안받지 않음??

[익명(1.240)]

명세 보면 이터레이터만 받는거로 보임 그래서 insert 자체는 상수시간임, 심지어 너가 직접 측정도 해봤잖아? 다만 맞는 위치를 찾아내는 연산이 선형시간이라 현실성 없다는 주장이 나오는거고

[수학최종보스(finalbossmath)]

그니까 상수를 받으니까 O(n)이 나왔던거네 상수면은 head부터 내가 입력한 pos만큼 1칸씩 node를 이동해야하니까

[수학최종보스(finalbossmath)]

c++이 아닌 다른 index를 받는 프로그래밍 언어에서는 O(n)을 받는거구만

[수학최종보스(finalbossmath)]

붙잡고 설명해줘서 감사