sgc109   3달 전

반환 타입이 벡터인 함수 내에서 벡터를 선언한뒤 안에 원소들을 막 넣은뒤 반환하면 시간복잡도가 어떻게되나요?

내부적으로 주소값을 통해 접근해서 O(1) 인가요? 아니면 일일이 복사해서 O(n) 인가요?

반환 자체도 O(n)이긴 한데, 내부에서 이터레이팅을 돌면서 벡터에 값을 채우는 반복문이 있다면 여기서 벌써 O(n) 아닌가요?

yukariko   3달 전

C++11 이전에서는 깊은 복사를 수행하기 때문에 O(N)이지만

C++11 부터는 얕은 복사를 통해 O(1)로 이루어집니다.

자세한 내용은 move semantics를 살펴보시면 될 것 같네요. 

sgc109   3달 전

portableangel 질문을 잘못한것같네요 ㅎㅎ 

제가 세그트리를 구현하는데 각각의 노드가 벡터를 가지고 있어야해서 init 함수가 vector<int> 를 반환하도록 했는데

벡터의 반환이 오래걸려봐야 O(n) 이기때문에 아무리 구간트리의 조상 노드가 가지고있는 벡터의 길이(?)가 길어져도(100만 이하) 크게 속도에 미치는 영향이 없나요?반환반환할때마다 lon(n) 이 걸리는데 반환을 최대2n 번 정도하니까 (?) (1+...+n/4+n/2+n)  속도에 혹시라도 영향을 끼칠까봐서요.. 

sgc109   3달 전

yukariko 와 어떻게 그런것까지.. 대단하십니다! 감사합니다

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