시간복잡도 강의 질문
시간복잡도 강의에서 n이 100만일 때를 가정해서 설명해주셨고, 상수는 무시한다라는 걸 확인했습니다.
만약, 0부터 n까지 도는 for문 하나가 100만개 있다고 가정하면, 이것 또한 상수를 무시해서 Big-O 표기법으로 O(N)이 되나요? 아니면 N * N이 되므로 O(N^2)이 되나요?
답변 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++) {
//...//
}
감사합니다.
백준 1940 주몽의 명령 시간복잡도
0
62
0
다음영상이 문제 풀이 영상이라고 하셨는데 문제풀이 영상이 누락되어있는 것 같습니다
0
129
1
코딩테스트 디버깅
0
352
1
탐색 순서 질문
0
149
1
[P11726 2*N 타일채우기] top down 방식을 사용하니 런타임 에러가 발생합니다.
0
106
1
2018 연속된 자연수의 합 구하기 백준 사이트에서 메모리 초과 오류가 발생합니다.
0
204
1
1강 시간복잡도 중간에 중첩for문 직전에 상수는 상관없어요 하신 부분이 이해가 안됩니다
0
162
1
왜 int, long은 안되는지 궁금합니다.
0
225
1
DNA 비밀번호 (백준 12891) 통과가 안됩니다.
0
528
2
LCA 빠르게 구하기 Java 코드 시간초과
0
245
1
스택문제 백준 1874
1
460
1
백준11659 구간합 런타임 에러
0
308
1
백준 2178 미로탐색 질문 입니다.
0
449
1
구간합구하기1 (백준11659)
0
424
1
혹시 다른 ide에서 잘 돌아가는 프로그램이
0
352
1
내림차순으로 정렬하기 강의에서..
0
273
1
백준 11720 숫자의 합 질문 있습니다
0
436
1
(숫자의 합)1<=N <=100 사이의 값
0
386
1
소수구하기-백준 1929 질문
0
351
1
12891_DNA비밀번호
0
635
3
숫자의 합 구하기
0
393
1
안녕하세요 질문있습니다.
0
338
0
union 코드에 질문 있습니다.
0
407
2
[그리디 실전 문제] 최솟값을 만드는 괄호 배치 찾기 (백준 1541) - 반례를 못찾겠습니다 ㅠㅠ
1
312
1