시간복잡도 관련
279
작성한 질문수 1
답변 2
0
답변 감사합니다.
그려주신 그림 기준으로 생각해보면,
LLL
LLL
LLL
가장 먼 정점에 도달하는 비용은 5번이지만
가장 먼 정점을 알아내기 위해서 모든 정점을 방문해봐야 아는 것이니, 그 부분을 시간복잡도(3*3)로 봐야 하는 것이 아닌가 해서요.
0
음 정확히 따지면
정점마다 bfs 시간복잡도 : 2500
>> 가 아니라 최악의 경우 2500 / 2 이긴 해요. 맵을 완전히
LLLLLL
WWWWW
LLLLL
이런식으로 나오게 되면 한번 BFS마다 맵의 반정도를 탐색해야하기 때문이죠.
but, 보통의 BFS로 잡으면 100, 50 * 2이가 됩니다. 가로, 세로를 더한 값입니다.
보통 최악 또는 평균값을 기반으로 시간복잡도를 정합니다.
해당부분 설명 추가하겠습니다.
자, 그러면 어떻게 100이냐?
위의 그림이 보통의 맵인데요. 이렇게 보통의 경우 저 마지막 정점, 제일 멀리 있는 정점까지 가는데 5정도밖에 걸리지 않습니다.
가로 세로 더한 값 - 1 인 셈이죠.
그렇기 때문에 50 * 2인 100으로 계산했습니다.
감사합니다.
1-E질문입니다!
0
533
2
3-L 틀린 부분 피드백 부탁드립니다.
0
835
2
1-A문제 순열재귀함수 질문입니다.
0
396
1
1-A 일곱난쟁이문제입니다
0
469
1
문제 풀 때 방향성에 대해
0
809
1
맥에서 vs code로 실행 관련 질문입니다
0
530
1
17071번 메모리 초과
0
389
1
1-C질문입니다!
0
428
2
2-B BFS 시간초과질문
0
637
2
1-O 13번 라인
0
445
1
6-J 놀이공원 문제 질문
0
388
1
구현관련 질문
0
491
1
강의 교안
0
321
1
실력을 더 올리고나서 강의를 보는 것이 맞을까요?
0
550
1
안녕하세요! 재귀함수에 관해서 질문드립니다
0
539
1
1-K
0
481
2
3-G번 질문있습니다.
1
480
3
3-C 실행 시간 질문드립니다.
0
502
1
4-A 문제 풀이 질문있습니다.
0
601
2
비트마스킹 연산자 "1의 보수" 영문 표기법
0
441
1
격자탐색 문제에서 BFS 시간복잡도 질문드립니다.
0
349
1
3-O go 함수 질문 드립니다.
1
452
2
4-A 출력 질문
0
307
1
1주차 1-O 질문드립니다
0
264
1