irnd04   5년 전

아무리 찾아봐도 나오질 않네요 ㅜ

어떤 알고리즘이 N * M + N log N 의 시간이 걸린다고 볼때

시간복잡도는 어떻게 쓰나요?

djm03178   5년 전

그걸 그대로 O() 괄호 안에 넣어주면 됩니다.

irnd04   5년 전

@djm03178 감사합니다 최고차항은 뭐 지운다고 해서 헷갈렸네요

cubelover_dev   5년 전

시간복잡도의 정의에 따르면 최고차항의 계수와 상수항 같은 걸 굳이 지울 필요는 없습니다.

O(N^2), O(2N^2), O(N^2 + 3N + 4) 등은 모두 같은 시간복잡도이며, 그 중 가장 간단한 O(N^2)을 적는 방식을 택할 뿐입니다.

질문하신 시간복잡도의 경우에는 더 간단하게 적을 수가 없기 때문에, 그대로 적으시면 됩니다.

irnd04   5년 전

@cubelover_dev

하나만 더 질문 하겠습니다.

위에 말씀하신

N^2 + 3N + 4 는 O(N^2 + N) 이 되는건가요 아니면 O(N^2)이 되는건가요

만약 후자라면 제가 질문한 시간복잡도는 O(NM)이 되는것이 아닌가요?


cubelover_dev   5년 전

셋 모두 동일한 시간복잡도이기 때문에, N^2 + 3N + 4는 O(N^2 + N)이면서 O(N^2)입니다.

질문하신 시간복잡도는 O(NM)이 아닙니다. N이 M에 비해 매우 큰 경우를 생각해 보세요.

djm03178   5년 전

O(N^2 + N)도 되고 O(N^2)도 상관 없습니다. 왜냐하면, N^2이나 N은 모두 N에만 의존하기 때문에, 더 빠르게 증가하는 N^2만으로 쓸 수 있기 때문입니다.

하지만 NlogN + NM은 이야기가 다릅니다. N이 크고 M이 작다면 NlogN이 복잡도를 지배할 테고, N이 작고 M이 크다면 NM이 지배하겠죠. N과 M 둘 다에 달려있는 사항이기 때문에 한 쪽을 생략할 수가 없습니다. 만일 이를 조금 바꿔서 NlogM + NM이라면 이건 O(NM)으로 써도 됩니다.

irnd04   5년 전

@cubelover_dev @djm03178 

궁금점이 풀렸습니다.

고맙습니다.

irnd04   5년 전

하나더 궁금합니다.

M * N log N으로 작성할수 있을까요?

djm03178   5년 전

그것도 안 됩니다. NM이라는 항은 N과 M 모두에 영향을 받는 거니까 하나만 자를 수 없죠.

irnd04   5년 전

@djm03178 

항상 감사합니다. !!

댓글을 작성하려면 로그인해야 합니다.