leehanjun   1달 전

문제는 최적화를 통해서 해결했습니다. 

그런데 문제를 풀면서 시간 복잡도에 대해서 질문이 있어서 질문을 남깁니다.

이전의 결과 값을 이용하여서 비교 값을 찾는 알고리즘을 실행했는데, 

이럴 경우에는 어떻게 시간 복잡도를 계산해야 하는 것일까요?  

때때로 입력 값: 9, 8, 7, 6, 5 에서 10이 들어가서 worst case가 되는 경우가 있는데, 어떻게 계산해야 하는지 모르겠습니다.

많은 분들이 O(N) 라고 계산하시는 이유가 무엇인가요?

tddhot2   1주 전

제 생각엔 문제를 푸는 원리가 삽입정렬과 비슷한 형태로 이뤄집니다.

삽입정렬의 최악 시간복잡도가 O(n^2)입니다.

아마도 최악의 경우 시간복잡도는 O(n^2)이지만

삽입정렬의 경우 데이터 실제 값에 따라 O(n)까지 효율을 낼 수 있는 것처럼

최악의 경우가 없는 대부분의 테스트 케이스가 문제의 테스트 케이스로 주어진거 아닐까 조심스럽게 생각합니다.

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