-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
시간복잡도 강의 질문
23.03.16 10:38 작성 조회수 620
1
시간복잡도 강의에서 n이 100만일 때를 가정해서 설명해주셨고, 상수는 무시한다라는 걸 확인했습니다.
만약, 0부터 n까지 도는 for문 하나가 100만개 있다고 가정하면, 이것 또한 상수를 무시해서 Big-O 표기법으로 O(N)이 되나요? 아니면 N * N이 되므로 O(N^2)이 되나요?
답변을 작성해보세요.
2
개발하는쿼카
2023.03.19
안녕하세요. 재영님
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++) {
//...//
}
감사합니다.
답변 1