글 읽기 - 시간복잡도 줄이는 방법 알려주실분 있으신가요?

n9805h 2년 전 0

1 배열 시간복잡도 = n

2 '' = 2n

3 '' = c

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

#include<iostream>
#include<vector>

using namespace std;

int main() {

	int n, a, b, c, d;
	cin >> n;

	vector<int> va;
	vector<int> vb;

	for (int i = 0; i < n; i++) {
		cin >> a; // 0 1 1 0
		va.push_back(a);
	} 

	for (int i = 0; i < n; i++) {
		cin >> b; // 1 2 3 4
		if (va[i] == 0) {
			vb.push_back(b);
		}
	}

	cin >> c; // 3
	for (int i = 0; i < c; i++) {
		cin >> d; // 2 4 7
		vb.insert(vb.begin(), d);
		cout << vb.back() << " "; // 4 1 2
		vb.pop_back();
	} 

	return 0;
}

drash99 2년 전 0

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

n9805h 2년 전 0

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

n9805h 2년 전 0

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

drash99 2년 전 0

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

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

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

문제

문제

출처

ICPC

시간복잡도 줄이는 방법 알려주실분 있으신가요?

n9805h 2년 전 0

drash99 2년 전 0

n9805h 2년 전 0

n9805h 2년 전 0

drash99 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말