1주차 개념 #4. 문제로 연습하는 시간복잡도 Q2

1주차 개념 #4. 문제로 연습하는 시간복잡도 Q2

다음 코드의 시간복잡도는 얼마일까요?

'아니 선생님 저희 그냥 지금까지 n 제곱, 이런 식으로 하나의 입력 값을 기반으로 시간 복잡도를 재지 않았나요?

지금처럼 N도 들어오고 M도 들어오면 어떡해요?'

그냥 여러분 더하시면 됩니다.

물론,

이런 식으로 N x M 의 시간복잡도가 발생할 수도 있어요.

그냥 이렇게 N 따로, M 따로 라고 생각을 하시면 돼요.

지금 이 코드의 시간복잡도는 정말 단순해요. 중첩되지 않고 그냥 나열되어 있으면 플러스 라고 보시면 되는데, N + M 이죠.

근데 만약에 이 코드가 이렇게 되어있으면 얼마일까요?

그러면 플러스가 아니라 곱하기 겠죠. NM의 시간복잡도를 가지는 거예요.

자 다시, 입력 값이 하나가 아니라 여러개가 들어오면 하나가 소거가 되는 게 아니라,

이걸 둘 다 동시에 나열을 한다라고 생각을 하면 되는 거예요.

그럼 여러분 제가 한번 문제를 내볼게요.

이러한 시간복잡도가 있는 코드가 있어요. 이거를 빅오 표기법으로 나타내면 어떻게 될까요?

그러면 이 입력 값(N)에 한에서 가장 큰 값(N^2), 이 입력 값(M)에 한에서 가장 큰 값(M^2)이 들어와서 이렇게 된다 라는 거예요.

그러니까 입력값이 두 개가 들어와도 당황하지 말고 그냥 나열한다고 생각하고, 이 둘이 만약에 중첩되어 있다? 그럼 곱하기고,

만약에 서로 중첩되어 있는 게 아니라 그냥 나열되어 있다, 떨어져 있다 그러면 N + M 이런 식으로 된다라는 겁니다.