10의 8승 시간복잡도 근본적인 이유
안녕하세요 강사님.
코딩테스트를 준비하거나 시험을 치를 때 지켜야 하는 시간복잡도를 왜 10의 8승인건지 근본적인 이유를 알고 싶습니다.
그냥 이 시간복잡도를 일종의 (관행적인 느낌의) 마지노선으로 두는 것인지요..
답변 1
1
안녕하세요 재영님.
근본적인 이유는 코딩테스트 시험장에서의 제한조건 때문입니다.
한번 삼성 코딩테스트의 시간 제한 조건을 볼게요
이렇게 1초 또는 2초정도로 되어있네요.
물론 코딩테스트마다 시간 제한은 다르겠지만 보통은 1초~10초 내외로 제한하는 편입니다.
그럼 보수적으로 실행시간을 1초 내로 줄여야 하는데,
사실 코테 서버의 CPU에 따라서 같은 코드라도 실행시간이 천차 만별이겠죠.
그래서 엄격하게 시간복잡도를 몇으로 해야된다 라는 것을 애초에 규정하기는 쉽지 않습니다.
하지만 대부분 관행적으로 10^8이내의 실행횟수에 대해서는 통과하도록 설계를 하는 편입니다.
제가 한번 제 컴퓨터에서 10^8의 실행횟수를 가진 코드를 실행해볼게요
보니까 약 1.78초 정도가 나오네요.
그래서 결론은 관행적으로 10^8을 지키면 통과한다~ 입니다.
좋은 질문 해주셔서 감사합니다.
혹시 풀리지 않은 의문점이 있으면 더 질문해주세요!
화이팅
노션 공유 링크
0
85
2
수업 중간에 내주신 문제는 해답을 알 수 없는걸까요?
0
75
2
최신 강의와 비교
0
83
2
Min Cost Climbing stairs 질문
0
75
2
노션 공유 부탁드립니다!
1
87
2
for 문에 sort 함수 를 사용하면
1
87
2
노션 공유 부탁드립니다.
0
102
2
디스코드가 올바르지 않다고 뜹니다..!
0
106
1
그래프
0
97
2
노션 공유
1
122
2
시간복잡도 질문
2
124
3
11강 질문
1
77
2
노션 공유 부탁드립니다
0
83
2
linkedList - BrowserHistory 코드 질문
0
75
1
list1.append(list2)와 list1.append(list2[:])의 차이가 무엇인가요?
1
166
1
라이브러리 사용
1
135
2
문제 교재는 따로 없는 거 맞나요?
1
201
2
LCA 관련해서 질문이 있습니다.
1
117
2
[Unique Paths] 완전탐색 / DP (후반부)
0
107
1
dp 계단오르기최소비용질문입니다.
0
107
1
Dynamic Array 의 size 정보가 저장되는 곳
2
161
2
노션공유가 안된듯 합니다
1
162
2
[코테 적용] 👉 [3번 문제] 완전탐색 (DFS, BFS) (전반부)
1
121
1
강의자료 만들 때 사용하신 프로그램이 뭘까요?
1
202
1