sgo8308   2년 전


N이 10이고 H가 30이라 가정할 때

dfs경우의 수만 270C3 하면 350만번 정도 나옵니다.

그리고 각 경우의 수마다 사다리를 타서 모두 자기 자신과 같은 숫자로 연결되는 지확인하는데 각 사다리마다 30번씩 10개해서 300번

350만 x 300 = 10억이 나옵니다.

사디리 타다가 일치하지 않는 거 나왔을 때 더 이상 진행하지 않는다고 해도

평균적으로 사다리 10개 중에 5개는 확인해야 한다면 5억번

거의 이정도 연산이 든다고 보이는데요


답은 맞았고 시간은 380ms가 걸렸는데, 어떻게 이 시간 안에 풀린건지 이해가 안되네요??

380ms면 대략 4000만번 연산에 끝났다난 의미 아닌가요?

 

0000000000   2년 전

1억회 연산 = 1초라는 기준은 정확한 게 아닙니다. 수행하는 연산이 매우 간단하다면 10억번은 1초 안에 수행할 수 있습니다.

sgo8308   2년 전

그럼 간단한 연산이 들어 있는 경우는 시간 복잡도에서 제외하고 시간복잡도를 생각하는게 나을까요?

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