아까 시간복잡도 올린 학생인데요 ㅠㅠ
만약 2중 루프에서
for(int i = 0; i<n; ++i){
for(int j = 0; j<n; ++j){
// 루프 내부엔 O(1)작업들만 존재한다.
}
}
라고하면 O(n^2) 이 맞죠?
왜냐하면 루프 2개가 전부 크기 n에 영향을 받기 때문이라고 알고있는데
그럼 내포된 루프가 n의 크기에 영향을 받지않는 연산의 반복이라면
for(int i = 0; i<n; ++i){
//루프 내부에는 10개의 연산이 있을수있고 10000개의 연산이 있을수있다. 모든 연산은 O(1)로 처리된다.
}
이경우, 루프안에 얼마나 많은 수의 작업들이 존재하더라도 이것은 O(n)으로 봐도 되는거죠?
제가 생각하는게 맞나요?
그럼 다른 케이스도 궁금한게 있습니다
for(int i = 0; i<n; ++i){
//m의 크기는 매번 여기서 정해진다. 굳이 말하자면 (m <= n)
for(int j = 0; j<m; ++j){
// 루프 내부엔 O(1)작업들만 존재한다.
}
}
여기서 n은 고정값이고 m은 매번 다른값을 가질때
이경우에는 어떤가요?
글쓰기