[일반] 알고스팟 와일드카드 시간복잡도 질문좀 드려도 될까요

[익명(123.212)]

https://gon109.tistory.com/m/52

첫번째 방법의 시간복잡도는 이해가 가는데

왜 두번째 방법의 시간복잡도가 n^2 일까요ㅠ

어차피 첫번째 코드랑 똑같은 방식으로 탐색하는거 아닌가요..?

[p플랫(urd05)]

함수 내부에서 반복문이 안 돌잖아요

[익명(123.212)]

반복문은 안돌지만, 전체를 탐색한다고 가정하면 결국 횟수는 똑같은게 아닌가요?

[익명(223.39)]

첫번째가 O(n^4)이고 두번째가 O(n^3)아님?

[익명(223.62)]

dp의 시간복잡도 : 상태 개수 * 각 상태에 대해 답을 구하는 시간 / 첫번째 방법 : 상태 개수 O(N^2), 각 상태에 대해 답을 구하는 시간 O(N) / 두번째 방법 : 상태 개수 O(N^2), 각 상태에 대해 답을 구하는 시간 O(1) - dc App