9-26[알고리즘] 시간복잡도 학습

TIL

시간 복잡도에 대한 복습 중 

알고리즘 관련 강의로 학습 중 점근 표기법과 빅오 표기법에 대하여 학습했던 기억이 있지만 해당 내용을 중요하게 생각하지는 않고 알고리즘 학습을 하고 있었다. 

 

이에 이해도가 부족한 것을 느끼고 시간 복잡도에 대한 추가 학습을 하였다.

 

- 시간복잡도와 공간 복잡도 간략 정리

두 가지 내용은 알고리즘을 평가할 때 사용

• 시간 복잡도: 알고리즘의 수행 시간을 평가
• 공간 복잡도: 알고리즘 수행에 필요한 메모리 양을 평가

시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅오 표기법을 이용

 

이렇게 하는 이유는 최악의 상황일 때의 수행능력을 생각해 볼 수 있기 때문이다.

여기서 빅오 표기법에 대해서 간략하게 설명하자면 점근 표기법에 대한 용어에 대한 설명도 생각해보아야 하는데 점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이며 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 사용하며 여기서 빅오라는 것은 무한급수증 상한 점근 즉 최대로 시간이 많이 걸리거나 공간을 많이 사용하는 경우를 생각하면서 추론하는 것을 나타낸다.

 

시간 복잡도 계산

연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차 항의 계수를 제외시켜 나타냄

입력값에 따라서 간단한 예를 생각해보면 

• S(n)=n2+2n+1=O(n2) : 최고차항만 표현
• S(n)=2n=O(n) : 최고차항의 계수는 제외

기본적으로 알고리즘을 만들 때의 고려점을 이중 for문 구성이 있는지 for문의 스텝 단위의 구성이 어떻게 되어있는지를 확인하면서 구성하면 되겠다.

이중 for문의 경우에는 위의 예시의 첫 번째 경우처럼 n*n의 경우가 되므로 n^2의 시간 복잡도를 갖게 되며 for문의 스텝이 반복될 때마다 2배씩 증가하는 구성 등이 있다면 수행 횟수에 대한 식을 나타냈을 때 2^k = n의 구성으로 반복문이 종료되게 되며 이때 수행 횟수인 k를 구하기 위하여 양쪽에 log를 취하게 된다면 log2를 취하지만 log10이라고 생각하고 걸리게 되는 시간 복잡도는 logN으로 생각할 수 있다.

 

시간 복잡도 표기

O(1) - 상수 시간 (Constant time), O(logN) - 로그 시간 (Logarithmic time), O(n) - 선형 시간 (Linear time)

O(n2) - 2차 시간 (Quadratic time), O(2n) - 지수 시간 (Exponential time)

등으로 표현하며 그 복잡도의 크기를 비교하여 나타내면 밑과 같다.

 

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)

 

공간 복잡도(Space Complexity)

사용하는 메모리의 양을 나타내는 것이다.

보통의 경우에는 시간 복잡도의 효율성 향상을 알고리즘 풀이에서 더 중요하게 생각하지만 재귀적인 함수 구성을 할 경우에 종료 조건 등이 제대로 구성되어있지 않을 때 스택 메모리 공간에 내가 알고리즘에 사용하는 함수나 변수의 값이 너무 크게 들어가서 depth 초과 문제 또는 depth 제한을 풀었을 때 스택 오버플로우 같은 문제를 야기시킬 경우가 있으므로 고려해야 할 경우가 있다.

 

알고리즘 문제풀이

https://dawnpast12.tistory.com/entry/ETC-%EC%9B%90%EC%9D%98-%EB%B0%A9%EC%A0%81%EC%8B%9D%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EB%B3%84%EC%B0%8D%EA%B8%B0

[ETC] 원의 방적식을 이용한 별찍기

https://dawnpast12.tistory.com/entry/ETC-%ED%8C%8C%EC%9D%BC-%EC%9D%B4%EB%A6%84-%EC%A0%80%EC%9E%A5%ED%95%98%EA%B8%B0

[ETC] 파일 이름 저장하기

https://dawnpast12.tistory.com/entry/ETC-%EC%9D%B4%EC%A0%84-%EC%88%AB%EC%9E%90%EB%93%A4%EC%9D%98-%ED%95%A9%EC%9D%84-%EB%A7%88%EC%A7%80%EB%A7%89-%EC%88%AB%EC%9E%90%EB%A1%9C-%EB%B0%9B%EB%8A%94-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%B6%9C%EB%A0%A5

[ETC] 이전 숫자들의 합을 마지막 숫자로 받는 문자열 출력

 

** 프로그래머스 - 양궁대회 문제 풀이 중