공간복잡도 질문입니다!
공간복잡도가 N인 경우는 큰 차이가 없다고 이해했습니다.
예제 코드에서도 29, 30 처럼 N인 경우를 확인하였습니다.
그렇다면 공간복잡도가 N^2인 경우는 어떤 예제 코드가 될 수 있을까요??
시간복잡도는 이해가 갔는데(ex. 이중for문) 공간복잡도가 N^2인 경우는 어떻게 되는지 궁금합니다!
답변 1
0
안녕하세요 Aurora 님 좋은 질문 감사합니다!
공간복잡도가 O(N²)인 경우를 실제 예제와 함께 설명해드리겠습니다.
가장 직관적인 예시는 N x N 크기의 2차원 배열(행렬)을 생성하는 경우입니다.
def create_multiplication_table(n):
table = []
for i in range(n):
row = []
for j in range(n):
row.append(i * j) # i와 j의 곱셈값을 저장
table.append(row)
return table
# n이 3일 때의 결과:
# [
# [0, 0, 0],
# [0, 1, 2],
# [0, 2, 4]
# ]즉 n(3) 이라는 입력값의 크기에 비해 n^2(9) 만큼의 영역을 차지하게 되므로 n^2 의 공간을 차지한다고 표현할 수 있을 것 같습니다!
더 궁금하신 점 있으시면 남겨주세요 좋은 질문 감사합니다!
수강평 이벤트
0
34
2
코딩테스트 처음인데 이런 공부방법이어도 괜찮을까요
0
70
2
3-3 정렬-2 선택정렬 로직
0
43
2
링크드 리스트 끝에서 k번째 값 출력하기
0
46
2
LinkedList 과제 Fast, slow 포인터
0
50
2
투포인터 시간복잡도
0
53
2
수강평 작성 후 자료
0
53
2
수업교재 링크 오류
2
114
2
프로그래머스에서 제출 후 채점시 틀림ㅠ
0
133
2
1-10 알고리즘 더 풀어보기(2) 질문 있습니다
0
76
2
문제 풀이 방식 관련 질문입니다!
0
88
2
1-5 알고리즘과 친해지기 (2) - 최빈값찾기 질문 있습니다
0
94
2
수업자료 pdf 받고싶습니다
0
108
2
강의 자료 오류 수정
0
75
1
2-10 더하거나 빼거나 관련 질문입니다
0
63
2
3-8 해쉬 -2
0
49
2
Linked List Element Delete Explanation Problem
0
69
2
강의3-4 스택 탑 문제
0
74
2
코드스니펫 입출력 케이스에 오류가 있는것 같아요
0
100
3
링크드 리스트 원소 찾기 구현 방식 질문드립니다.
0
76
2
1874 - 스택 문항
0
81
2
DP Java 예제 자료형 오버플로우 문제
0
100
2
4-9 4주차 숙제중 농심라면 문제
0
111
2
DFS 에서 스택을 사용하는 이유
1
187
3