Inflearn Community Q&A
asked
시간복잡도 강의 질문
Resolved
Written on
·
890
1
시간복잡도 강의에서 n이 100만일 때를 가정해서 설명해주셨고, 상수는 무시한다라는 걸 확인했습니다.
만약, 0부터 n까지 도는 for문 하나가 100만개 있다고 가정하면, 이것 또한 상수를 무시해서 Big-O 표기법으로 O(N)이 되나요? 아니면 N * N이 되므로 O(N^2)이 되나요?
java코딩-테스트알고리즘
Answer 1
2
안녕하세요. 재영님
N 까지 반복하는 loop가 1개라면
시간복잡도는 O(N) 입니다.
for(int i = 0; i < n; i++) {
//...//
}
N 까지 반복하는 loop안에 또 N까지 반복하는 loop가 존재한다면 시간복잡도는 O(N^2) 인것으로 알고 있습니다.
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
//...//
}
}
만약 아래와 같으면 상수는 무시하기 때문에
O(N)으로 표기하는 것으로 알고 있습니다.
for(int i = 0; i < n; i++) {
//...//
}
for(int i = 0; i < n; i++) {
//...//
}
감사합니다.
죄송합니다 답변을 너무 늦게 봤네요
답변 정말 감사합니다!