zodist   4년 전

안녕하세요 일단 문제를 풀긴 했는데 궁금한 게 생겨서요

제가 이해한 바로는 O(N*M)의 시간 복잡도가 계산되는데요 (빅오는 최악의 케이스니까)

그럼 O(50000 * 10000) = O(5억) 이 됩니다. 대략 1억번의 게산을 1초에 할 수 있으니까 엄밀히 말하면 1초 안에 해결할 수 없는 거 아닌가요?

답변해주시면 감사하겠습니다

exqt   4년 전

어디까지나 1억 1초는 대략적인거지 절대적인 기준이 아닙니다.

캐싱이나 컴파일러 최적화에 따라 성능이 달라질 수 있고 요즘 컴퓨터는 10^9 반복문이라도 단순한 계산이면 1초에 돕니다.

teayk123   4년 전

윗분보다 논리적으로 말씀드리면

트리가 정~~말 극단적으로 일렬로 쭉~연결되어 있는 배열형태의 트리가 아니라면

O(logn)의 시간복잡도를 가지게 됩니다. 예를 들어서 단순하게 완전 이진 트리라고 하면요.

노드의 개수가 N개일때 높이는 logN입니다. 이때 로그는 밑수가 2겠죠.

트리 그림을 한번 그려보시고 제일 바닥의 노드부터 루트까지 몇칸올라가면 되는지 세어보세요.

문제의 예제에서는 한 노드에 3개의 자식노드가 있기도 하니까 디테일하게 보면

logN보다 더 적은 시간복잡도를 가질것으로 예상됩니다.(물론 엄청 미비하게 작겠지만요)

그래서 아마 이 문제에서 주는 예제가 

한노드에 하나의 자식노드만 이어진 배열형태가 아니라면

log 50000 * 10000 (이때 로그는 밑수가 2)

= 15만6천 정도

1초안에 쌉가능

windflower   4년 전

@teayk123 님 의견이 완전히 틀린 말씀은 아니시지만 맞는 말씀도 아니라고 생각해 답글 드립니다.

문제에서 이진트리라는 조건이나 특변할 조건이 없다면 우리는 최악의 경우인 일자 트리나 그와 비슷한 모양의 트리를 반드시 생각해야 합니다.

따라서 일반적인 LCA 문제에서는 sparse table을 활용하여 사전작업 nlog(n), 쿼리당 log(n)이라는 복잡도로 문제를 풀게 됩니다.

11437문제에서는 복잡한 계산이 없어 1초 안에 통과하지만 다른 트리 문제에서 이렇게 위험한 가정으로 문제를 풀었는데 통과한다면 데이터가 약한 것일 수 있습니다.

jh05013   4년 전

exqt님 답변이 맞습니다. 개인적으로 "1초에 1억 번"이라는 말은 옛날 말이라고 생각합니다. O(N^2)에 N <= 10,000인 문제라고 해서 1초 꽉 채워서 돌진 않으니까요. 3억 번 정도까지 생각해도 무방하고, 가벼운 연산은 더욱 빨리 할 수 있습니다.

온라인 저지에서는 최악의 케이스가 입력으로 들어올 수 있기 때문에 최악의 시간 복잡도를 고려해야 합니다.

teayk123   4년 전

@windflower 제가 짧은 지식으로 섣부른 가정을 한것같네유,ㅠㅠ 피드백 감사합니다.

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