안녕하세요! 실습 막바지라, 이것저것 커밋할게 너무많아 이틀이나 포스팅을 쉬어버렸네요ㅠㅠ
그래도 오늘 다시 포스팅 해보도록 하겠습니다!
음, 오늘 주제는 시간복잡도와 공간복잡도로 정했어요ㅎㅎ
개발자에게서 뗄래야 뗄 수 없는 개념이죠!
제가 지금부터 포스팅 할 시간복잡도와 공간복잡도는 모두 알고리즘의 수행과 관련하여 사용하는 용어입니다.
그렇다면, 알고리즘이 무엇인지부터 정의해야겠죠?ㅎㅎ
알고리즘은 일상생활에서도 익히 들었고, 고교생활에서도 충분히 들었을 단어입니다.
하지만, 저는 컴퓨터공학과에 진학 전에는 알고리즘에 대해서 지금 아는 것과는 다르게 막연히 생각하고 있었어요!
나 : 알고리즘이란? 음, 정의역에 맡는 대입값을 넣으며 문제를 해결하는 과정.
딱 이정도!ㅋㅋㅋ
제가 처음 알고리즘을 접했던 것은 수학적 점근법(?)을 처음 배울 때,
An+1 = An + 1 과 같은 문제를 푸는 과정에서 였습니다. 기억나시죠?ㅋㅋ
그렇다보니, A2=A1+1 ,A3=A2+1 , 이런식으로 계산하면서 풀어나갔습니다. 그래서 저정도로만 생각했어요!ㅎㅎ
그러면, 제가 생각한 정의가 아닌 진짜 정의를 발췌하자면,
알고리즘(algorithm)은 주어진 문제를 논리적으로 해결하기 위해 필요한 절차, 방법, 명령어들을 모아놓은 것입니다. 넓게는 사람 손으로 해결하는 것, 컴퓨터로 해결하는 것, 수학적인 것, 비수학적인 것을 모두 포함
출처 : [네이버 지식백과] 알고리즘 [algorithm] (천재학습백과 초등 소프트웨어 용어사전)
음, 제가 생각한 것은 수학적인 것에 국한되는 것 같네요!
결국은 과정이라는 것!
그러면, 그 과정을 수행하며 걸리는 시간과 그 과정을 수행하는데에 사용한 일의 양(?)이 존재할 것이고,
시간이 짧고, 일의 양이 적을수록 좋은 알고리즘이라고 할 수 있겠죠?(인간은 유한한 시간과 자원 속에서 사니까요!ㅎㅎ)
이 때, 제가 일의 양이라고 표현한 것이 컴퓨터로 해결할 때엔! '공간복잡도'라고 할 수 있겠습니다.
컴퓨터로 과정을 수행하는 것은, 컴퓨터가 메모리를 사용하여 계산을 하는 것입니다.
따라서, 공간복잡도란, 메모리 사용량에 대한 결과라고 할 수 있겠습니다.
그럼 공간복잡도는 알았으니, 어떻게 과정을 수행하며 걸리는 시간을 계산할까요?
컴퓨터로 과정을 수행할 때엔, 인간이 하기힘든 정도의 작업량,계산의 복잡함 등이 존재할 때 입니다.
(1+2+3 같은건 컴퓨터보다 사람이 하는것이 나으니까요^^)
그렇다면, 거의 무한에 가까운 수를 더하고 곱하는 일도 있을거고, 반면, 아주 적은 계산일수도 있습니다.
엄청난 양의 계산을 할 때엔, 그 시간을 어떻게 정의할 것인가를 고민할 수밖에 없을 것입니다.
그 시간을 계산할 때에, 아주 많은 양의 처리에서 소모시간을 결정하는 3가지 방법이 있습니다.
바로 예상 소모시간의 최악,최선,평균을 구하는 방법입니다.
소모시간의 평균을 구하는 것이 가장 이상적이지만, 그것은 매우 복잡하여, 최악의 시간을 계산하는
빅오표기법(Big O)을 주로 사용합니다.
빅오표기는 연산횟수를 매개변수로 O(n^2 + n + 1)과 같이 표기하며,
이 때, 충분히 큰 n에 대하여, 최고차항만을 고려한다.
따라서 위의 표기는 O(n^2)과 같다.
또한, 빅오표기의 크기비교는 다음과 같다.
O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
출처: https://ledgku.tistory.com/33 [견우와 직녀]
O(1)에 가까울수록 효율적인 알고리즘이라고 칭합니다.
제 포스팅은 항상 10%부족한 것 같아요ㅠㅠ 그만큼 제 이해도가.. 떨어지는 것이겠지만,
알고리즘 책을 처음 보고, 정리하면서 다시 보는게 저한테는 큰 도움이 됩니다.
(처음엔 빅오고뭐고,, 감도 안잡혔거든요..ㅎㅎ)
저한테 도움이 됐듯, 누군가에게는 이정도의 설명이 더 적절한 설명이길 바라며
오늘의 포스팅을 마칩니다.
감사합니다^^