n9805h   8달 전

1 배열 시간복잡도 = n

2 '' = 2n

3 '' = c

따라서 시간복잡도는 O(n)인데, 더 줄일 수가 있는건가요??

drash99   8달 전

c++ vector에서 insert는 O(n)입니다. 그래서 느려요. 대신 deque 찾아보시면 될거에요

n9805h   8달 전

감사합니다! 바로앞에서 시작하면 n번 반복해야 O(n)인줄 알았네요

n9805h   8달 전

vector도 맨앞과 맨뒤는 O(1)이라고 나옵니다...

drash99   8달 전

혹시 그거 보신 소스가 어디인가요??

https://stackoverflow.com/ques... 이 글이 잘 나타내는 거 같아요. vector는 array로 구현되어있기에 뒤에 붙이는 것은 쉬워요. 하지만 앞에다 삽입을 하려면 모든 내용물을 오른쪽으로 한 칸 옮겨서 앞에 빈 공간을 만들어야 해요. 그러기에 O(n)이 걸리게 되고 느릴 수밖에 없죠.

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