malbong   4년 전

알고리즘 초짜입니다

머릿속에서 시간복잡도 계산을 하는 연습을 하고 있습니다


n값을 보니 최댓값이 커서 O(n^2)으로는 구현하지 못하겠다 생각은 했지만 아래처럼 구현 했습니다

(i = 0부터 n까지 비교해서 더 크면 배열에 넣음)

당연히 시간초과였습니다 그래서 스택으로

뒤에서부터 i > top이면 pop하는 아니면 오큰수로 배열에 넣는 형식으로 구현했는데요...

이러한 경우 시간복잡도는 어떻게 되나요...

입력이

5 1 2 3 4 5 에서

i=0 일때는 스택을 끝까지 top하고 비교하고 pop하는 최악의 상황인것 같고

i가 0이 아니면 나머지는 그냥 바로 top하고 한번만 비교하면 끝나는 경우고

  1. 이러한 경우 시간복잡도는 어떻게 머릿속에서 생각하나요???

 2.또한 n^1 n^2 n^3, n^m제외하고 NlogN, N! 같은 경우는 어떠한 경우인가요???

djm03178   4년 전

O(N)입니다. 프로그램 전체에서 21번째 줄의 루프가 도는 횟수는 O(pop이 일어나는 횟수)이고, pop이 일어나는 횟수는 O(push가 일어나는 횟수)인데 push는 O(N)번밖에 일어날 수 없으니 21번째 줄의 루프도 프로그램 전체를 통틀어 O(N)번만 돌게 됩니다.

malbong   4년 전

감사합니다

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