시간복잡도 질문
456
25 asked
안녕하세요. 좋은 강의 감사합니다.
island 카운트 세는 문제에서 시간복잡도를 n^2으로 풀면 안된다고 하셨는데 풀이법에서는 이중포문으로 푸셨더라구요.
이중포문은 시간복잡도를 n^2으로 알고 있는데 이렇게 푸신 이유가 있으신가요?
Answer 2
0
네 제가 보기에는 모든 데이터를 완전탐색으로 순회했기 때문에 사실상 O(n)입니다. 반면에 1차원 배열의 최대 데이터도 n이라고 가정했을 때, 여기에서 이중 for문을 사용하면, 한번 쭉 탐색했던 것을 중복해서 탐색하기 때문에 n(데이터의 수) * n(탐색 횟수) = n^2이라 O(n^2)의 시간복잡도가 걸린겁니다.
-1
안녕하세요, 인프런 AI 인턴이에요. 이중 포문은 시간복잡도가 O(n^2)입니다. 이렇게 푸신 이유는 island 카운트 세는 문제에서, 각각의 섬을 찾기 위해 모든 요소를 탐색해야 하는데, 모든 요소를 한 번씩 돌아야 하기 때문입니다. 따라서 이중 포문을 사용하여 해결하셨을 겁니다. 하지만 보다 효율적인 알고리즘을 사용하여 시간복잡도를 개선할 수도 있습니다. 이 부분은 성능 개선에 대한 고려사항이 될 수 있는데, 강의에서는 그런 부분을 다루지 않았을 수도 있으니 참고해주세요.
다른 질문이 있으시면 언제든지 물어보세요. 좋은 공부 되시길 바라요~요.
노션 공유 링크
0
83
2
수업 중간에 내주신 문제는 해답을 알 수 없는걸까요?
0
73
2
최신 강의와 비교
0
79
2
Min Cost Climbing stairs 질문
0
74
2
노션 공유 부탁드립니다!
1
84
2
for 문에 sort 함수 를 사용하면
1
85
2
노션 공유 부탁드립니다.
0
100
2
디스코드가 올바르지 않다고 뜹니다..!
0
103
1
그래프
0
94
2
노션 공유
1
121
2
시간복잡도 질문
2
121
3
11강 질문
1
74
2
노션 공유 부탁드립니다
0
81
2
linkedList - BrowserHistory 코드 질문
0
71
1
list1.append(list2)와 list1.append(list2[:])의 차이가 무엇인가요?
1
164
1
라이브러리 사용
1
133
2
문제 교재는 따로 없는 거 맞나요?
1
199
2
LCA 관련해서 질문이 있습니다.
1
116
2
[Unique Paths] 완전탐색 / DP (후반부)
0
102
1
dp 계단오르기최소비용질문입니다.
0
106
1
Dynamic Array 의 size 정보가 저장되는 곳
2
158
2
노션공유가 안된듯 합니다
1
160
2
[코테 적용] 👉 [3번 문제] 완전탐색 (DFS, BFS) (전반부)
1
117
1
강의자료 만들 때 사용하신 프로그램이 뭘까요?
1
195
1