1. 프로그래밍에서 복잡도란?

1. 시간복잡도

컴퓨터과학 용어로, 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 일반적으로 시간 복잡도와 로직의 수행시간은 비례하므로 시간 복잡도 수치가 작을 수록 효율적인 알고리즘임을 뜻한다.

• 시간복잡도의 표기법
  • 시간 복잡도는 보통의 경우 점근 표기법으로 사용되는데 주로 사용되는 점근 표기법은 아래와 같이 3가지가 있다.
• Big-O 표기법 / O(N): 빅오 표기법은 알고리즘 '최악'의 실행시간을 표기한다.
• Ω 표기법 / Ω(N): 오메가 표기법은 알고리즘 '최상'의 실행시간을 표기한다.
• Θ 표기법 / Θ(N): 세타 표기법은 알고리즘 '평균'의 실행시간을 표기한다.

Q. 위의 3가지 중에서 일반적으로 많이 사용되는 점근 표기법은 Big-O표기법이다. 왜 하필 '최악'의 실행시간을 나타낸 빅 오 표기법을 실제로 가장 많이 사용할까??

A. 알고리즘이 최악의 경우에 얼마나 느린가를 고려하여어떤 알고리즘을 이용해야 실행시간을 줄일 수 있을지를 판단 할 수 있기 때문이다.

빅오 표기법

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

2. 공간복잡도

작성한 프로그램이 얼마나 많은 공간(메모리)를 차지하느냐를 나타낸 것 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구 Q. 고정 공간 예시를 들어보세요

A. 코드 저장 공간, 단순 변수, 상수 등...

Q. 가변 공간 예시를 들어보세요

A. 함수의 순환 호출 시 요구되는 추가 공간 등

Q. 시간복잡도와 공간복잡도의 관계는 무엇이고, 왜 이러한 관계가 되는지 설명해 보시오.