시간복잡도, 공간복잡도

시간복잡도 파악법을 알아보자.

Input에 변화를 줬을때, 결과를 연산하는데 얼마큼 변하냐는 의미이다.

작성한 코드에서, 가장 큰(복잡한) 연산 기준으로 판단하면 된다.

O(x) 표기법 자체가, 최고차항 외에 딴건 안보겠다는 의미이니까.

 

 

△outPut/
△input

입력 n에 대해서

1. O(1) : n과 상관없는 연산 ex) print()

 

2. O(logN) : n 증가에 따라 결과는 log N 만큼 증가하는 연산(log의 밑은 변화할 수 있다. log란 것이 중요하다)

ex)for(i=0; i<n ; i*2){}

n이 T만큼 증가하면, 횟수는 T/2 만큼 증가한다. 즉, 지수의 역, 1-> (1/2) 증가하는 것이다.

 

3. O(N) : N에 비례한 연산, N의 변화만큼 결과도 똑같이 연산을 더한다. 

ex) for(i=0; i<n; ++i) {}

 

4. O(N^2) : N의 변화만큼 결과는 N^2 연산해야한다.

ex) 2중 for 문

 

5. O(2^N) :N의 증가에 따라, 결과는 2^n 연산해야한다.

ex) 피보나치수 구하는 알고리즘을 재귀적으로 구현.

f(n) = f(n-1)+f(n-2) 이므로, n이 올라갈때 연산이 2^n 씩 다단계 처럼 늘어난다.

 

6.O(n!) : 생략

 

구하는 방식을 이해하면, 자유롭게 표기 가능하다.

 

 

 

https://yoongrammer.tistory.com/79

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)

 

 

1. 기본 연산의 실행 횟수로 수행 시간을 평가

 

시간 복잡도는 일반적으로 빅오 표기법으로 나타냅니다. 연산 횟수가 다항식으로 표현될 경우, 최고차항의 승수로 표시합니다.

 

1. 데이터 입출력 - copy, move...
2. 산술 연산 - add, multiply ...
3. 제어 연산 - if, while ...

ex) 2중 for문 {} + for문{} = n^2 + n => O(N^2)

 

 

 

 

2. 각 시간복잡도 별 예시

O(1) - 상수 시간 (Constant time)

입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)입니다.

void func (int n) {
printf("%d\n", n);
}

 

O(logN) - 로그 시간 (Logarithmic time)

입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)입니다.(; i*2)

for(i=1; i<=n; i*2) {
... 
}

위 알고리즘은 i 값이 반복할 때마다 2배씩 증가합니다. 이것을 k번 반복했을 때 다음과 같습니다.

2k=N 

 

O(n) - 선형 시간 (Linear time)

입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간 복잡도는 O(n)입니다.

• 연산횟수가 선형적으로 증가하는 형태

for(i=0; i < n; i++) {
  ...
}

 

O(n2) - 2차 시간 (Quadratic time)

입력 크기(n)가 커질 때 연산 횟수가 n2에 비례해서 증가하면 시간 복잡도는 O(n2)입니다

for(i=0; i < n; i++) {
  for(j=0, j < n; j++) {
    ...
  }
}

 

O(2^n) - 지수 시간 (Exponential time)

입력 크기가 커질 때 연산수가 2^n에 비례해서 증가하면 시간 복잡도는 O(2^n)입니다.

int func (int n) {
	if (n <= 1) return n;
	return func(n-1) + fun(n-2);
}

 

공간 복잡도(Space Complexity)

사용하는 메모리 양

보조공간(Auxiliary Space) + 입력 공간(input size)

보조 공간(Auxiliary Space)은 알고리즘이 실행되는 동안 사용하는 임시 공간입니다.

그렇기 때문에 입력 공간(input size)을 고려하지 않습니다

 

공간 복잡도도 시간 복잡도와 유사하게 빅오 표기법을 사용합니다.

int sum(int a[], int n) {

int x = 0;
	for(int i = 0; i < n; i++) {
		x = x + a[i]; 
	} 
return(x); 
}

• int arr[n] : 4*n byte (입력 공간)
• int n : 4 byte (입력 공간)
• int x : 4 byte (보조 공간)
• int i : 4 byte (보조 공간)

총 4n+12 에 메모리를 요구합니다. 메모리가 입력 값에 따라 선형적으로 증가하기 때문에 공간 복잡도는 O(n)