알고리즘에 대해 공부하다보면 가장 먼저 부딪히는 2가지가 있다.
바로 알고리즘과 시간복잡도인데 알고리즘이야 평소 우리가 많이 사용하는 단어 이다보니 대충 무슨 느낌인지는 다들 알 수 있을것이다
ex) youTube의 알고리즘이 나를 여기로 이끌었다... 등등
그럼 시간복잡도는 무엇일까?
이번 글에서는 시간복잡도에 대해 알아보고자 한다.
시간복잡도란 어떠한 문제를 풀어맺기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다
위키피디아
당연히 들어도 무슨소리인지 모르겠으니 간단하게 말하자면
알고리즘을 푸는데 걸리는 시간을 의미한다.
즉 어느 한 문제 해결을 위한 알고리즘이 얼마나 간단한지, 복잡한지를 표시하는 지표라 할 수 있을것이다.
선택 정렬 Selection sort
은
첫번째 i
에서 1 ~ n-1
번
두번째 i
에서 2 ~ n-1
번
...
총 n(n-1)/2
즉 O(n²)
의 시간복잡도를 가진다.
?
n(n-1)/2
이면 ½n²-½n
이지 왜 O(n²)
라고 할까?
이는 시간복잡도를 계산하는데 있어서 가장 중요한 것은 핵심이 되는 연산을 찾는 것이기 때문이다.
½n²-½n
에서 n
이 커지면 커질수록 ½
이나 -½n
은 n²
입장에서 무시해도 될 정도로 작은 수가 될 것이다. 때문에 핵심이 되는 n²
이라고 쓰며 앞에 O
를 붙혀 Big-O
표기법이라 부른다.
시간복잡도와 Big-O에 대해서 이해하였으니, 이제 간단히 시간복잡도를 계산하는 법에 대해 알아보자,
for ( let i=0; i<n; i++ ) {
for ( let j=0; i<m; j++ ) {
}
}
위 식의 시간복잡도는 어떻게 될까?
정답은 바로
n²
이다.
왜냐면 무한한 수인n
과m
을 반복하는 반복문 2개가 있기 때문이다.
for ( let i=0; i<n; i++ ) {
for ( let j=0; j<m; j++ ) {
for ( let k=0; k< 100000; k++ ) {
}
}
}
그럼 위 식의 시간복잡도는 어떻게 될까?
정답은 바로
n²
이다.
왜냐면k
는 100000까지라는 유한한 수까지만의 반복이기 때문우리 눈에 100000은 큰 수처럼 보이지만, 무한한 수인 `n`과`m`입장에서 100000라는 수는 무시해도 될 만큼 작은 수라는 것을 언제나 인지해야한다.