-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
O(n)풀이법 질문입니다.
23.04.03 21:50 작성 조회수 290
1
leetcode의 다른사람의 답을 보다가 시간복잡도가
O(n)이 걸렸다고 쓴 사람의 코드를 보았습니다.
def uniquePaths(self, m, n):
if not m or not n:
return 0
cur = [1] * n
for i in range(1, m):
for j in range(1, n):
cur[j] += cur[j-1]
return cur[-1]
1차원 배열을 초기화하는 방법을 사용하셨는데 제가 봤을 때 이 방식도 시간복잡도 O(m *n) 이라 생각이 들어 질문을 드립니다.
이 분의 코드 시간복잡도가 O(n)이 맞나요??
답변주시면 정말 감사하겠습니다.
답변을 작성해보세요.
0
개발남노씨
지식공유자2023.04.05
안녕하세요. 코먹하님
코먹하님의 예상대로 1차원배열을 썼더라도 결국엔 O(M*N)의 시간복잡도가 걸립니다!!
1차원 배열을 써서 공간복잡도를 O(M*N) => O(N)으로 낮춘것에 의의가 있는 코드입니다~
또 궁금하신점 있으시면 언제든 질문해주세요!
답변 1