chlghksdyd24   8일 전

안녕하세요. 코딩 초보입니다.

다름이 아니고, python3에서는 시간 초과가 떳는데 왜 시간 초과가 떳는지 모르겠어서 질문 드립니다.

일단, 제가 계산한 나올 수 있는 큰 시간 복잡도는 2개인데요 첫 번째 시간 복잡도 1 = 1번 * 2번 * 3번 * 4번 , 두 번째 시간 복잡도2 = 1번 * 2번  * 5번  입니다.

(번호는 코드에서 주석으로 표시했습니다. ex) ###@@ 1번 @@### )

시간 복잡도 1 = 50 * 50 * (50 * 50) *4 = n * m * (n * m) * 4 방향       (3번이 n*m인 이유는 bfs 탐색에서 큐에 담길 수 있는 최대 개수는 행렬의 크기(즉, 전체)라고 생각하기 때문입니다.)

시간 복잡도 2 = 50 * 50 * (50 * 50) = n * m *(n * m)      (5번이 n*m인 이유는 3번과 마찬가지 입니다.)

그러면, 각 시간 복잡도를 계산하면. 시간복잡도 1 = 25,000,000 (이천 오백만),   시간복잡도 2 = 6,250,000 (육백 이십 오만) 이 각각 나오는데.

주어진 시간은 2초이니까 컴퓨터가 보수적으로 잡아 1초에 1억번의 연산을 한다고 치면, 2초 * 1억 = 2억번의 연산이 가능하니까 시간 복잡도가 범위 내라고 생각 했는데 시간 초과가 떠서 제 시간 복잡도 계산 방식에 오류가 있는 거 같습니다. (물론 각 for문 마다 1번 이상의 연산을 하지만 이 부분 까지는 고려하지 않았습니다.   ex)  O(5n2) = O(n2) )

답변 달아주시면 정말 정말 감사하겠습니다!


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