시간복잡도 문의드립니다.

Question

회사에서 간단한(?) SNS 서비스 설계 중에 네이버 D2에 좋은 글이 있어서 참고 중인데요. 링크 : https://d2.naver.com/helloworld/551588 여기서 설명하는 시간복잡도가 이해가 안되어서, 선배님들께 문의를 드리고자 합니다. 1.작성자 OR 굴비 알고리즘의 연산 비용을 계산해 보자. 내가 따르는 친구의 수를 m이라 하고 전체 사용자 수를 n이라고 한다면 전체 사용자 검색 연산의 시간 복잡도는 O(m log(n))이 된다. -> 내가 따르는 친구 m이 배열일 때, 내가 따르는 친구 1명이 작성한 피드를 조회한다면 select * from 피드테이블 where 따르는친구 &#61; m[0]; 이런 형태일거 같은데요. -> 만약 &#34;따르는친구&#34; 필드가 인덱스로 저장되어 있다면, 인덱스의 자료구조는 B-Tree 형태라서, 트리 형태를 조회한다. -> 따라서 내가 따르는 친구 1명을 where 조건으로 조회하는 경우 O(log n) 의 시간복잡도를 가진다. -> 내가 따르는 친구의 수가 m이면, where절에 or로 조건을 줘야하고 m 회 만큼 O(log n)이 실행되므로, 결국 O(m log n) 만큼의 시간복잡도를 가진다. -> 만약 &#34;따르는친구&#34; 필드가 DB 인덱스가 아니라면, 1명에 대해 조회할 때 O(n) 의 시간복잡도를 가질 것이다. -> &#34;따르는친구&#34; 필드가 DB 인덱스가 아닐 때, where절에 or로 여러명(m회) 조회한다면 O(mn)의 시간 복잡도를 가질 것이다..? -> 제가 이해한게 맞을까요? 2.일반적인 게시판 페이징 오퍼레이션에 비해서 상대적으로 얼마나 무거운지 비교해 보자. 전체 게시물의 수를 l이라고 한다면 게시판 페이징 비용은 O(log(l))이다. 사용자별 평균 보유 게시물 수를 k라고 한다면, l은 k * n이기 때문에 사용자 검색과 게시판 페이징 연산 비용의 비교는 O(m log(n)) 대 O(log(kn))로 나타낼 수 있다. 사실, 정확하게 Big O 분류 관점에서 m과 k는 상수로 볼 수 있기 때문에 두 복잡도는 같다고 볼 수 있다. 하지만 굳이 시간 비용을 비교해 보자면 m 대 log(k)/log(n)&#43;1, 즉 평균 친구 수 대 log(사용자별 평균 보유 게시물 수)/log(전체 사용자 수) &#43; 1이다. -> 게시판 페이징 비용은 O(log(l))이다. -> 이 내용은 1페이지당 게시물을 50개씩 보여준다면 50개씩 그룹을 나누어 조회하므로, O(l)이 아니라, O(log(l)) 인 것으로 이해했습니다. -> 그 이후 &#34;O(m log(n)) 대 O(log(kn))&#34; 여기 까지는 이해 했는데요. -> 결과적으로 어떻게 &#34;m 대 log(k)/log(n)&#43;1&#34;이 나오는지 이해가 되지 않습니다............ ㅠㅠ문의 내용 답변을 주셔도 되고 혹시 좋은 자료가 있으면.. 공부 해보려고하니, 자료 링크 추천해주셔도 감사드리겠습니다.항상 좋은 하루 되시길 바랍니다 ㅎㅎ

jslovers · Answer

m log(n) : log(kn)log(kn) &#61; log(k) &#43; log(n) 이므로m : log(k) / log(n) &#43; log(n) / log(n)m : log(k) / log(n) &#43; 1

Constant · Answer

1번은 잘 이해하신게 맞는거같은데요.. 저도 그렇게 밖에 이해가 안돼요.

시간복잡도 문의드립니다.

2개의 답변

Q&A 목록