2-T. 번 강의 질문 스택 풀이시 시간복잡도

작성한 질문수 10

0

안녕하세요 ㅎㅎ

그게 아니고, N+N 이 되는걸까요?

>> 네 맞습니다. 예를 들어 최악의 경우를 생각해봤을 때 저 while문이 최대치로 도는 경우는... 계속해서 pop이 안되는 경우겠죠.

그렇다면 for문으로 N번 돌았을 때 그대로 stack에는 N개가 쌓이다가 마지막 N개에서 POP을 하게 됩니다.

이경우 FOR문 N번, STACK에 쌓인 N개의 요소들을 POP하게 되어 총시간복잡도 2N = O(N)이 되게 됩니다.

감사합니다.

0

안녕하세요!!

만약 4,3,2,5 라는 입력이 주어지면

스택에 3개가 쌓이고, 쌓인 스택에서 while 문을 통해 순서대로 ret 배열에 값을 넣어주게 되니까 N^2 이라 생각했는데

그게 아니고, N+N 이 되는걸까요?

감사합니다.^^

0

안녕하세요 성욱님ㅎㅎ

시간복잡도는 여전히 O(N^2). 인 것 아닌가요?

>>

	for(int i = 0; i < n; i++){
		cin >> a[i];  
		while(s.size() && a[s.top()] < a[i]){
			ret[s.top()] = a[i]; s.pop();
		}
		s.push(i);
	}

음.. 혹시 이게 N^2라고 생각하시는 이유가 있으실까요?

감사합니다.