FE 개발자를 위한 안드로이드 후려치기 #3 자바스크립트 인터페이스로 새로운 웹뷰 액티비티 띄우기
2023-08-02
자바스크립트로 알아보는 알고리즘 #1 시간 복잡도
2019-03-02
Explanation
다시 찾아온 연휴! 오늘은 알고리즘에 관련해서 공부를 좀 해보려고 합니다.
그 첫번째로 시간 복잡도에 대해 알아 보려고 합니다. 일단 이렇게 서론만 써놓고 인터넷 이곳 저곳을 돌아다니며 공부를 해야하는데요, 살짝 둘러보니 수학적인? 용어?가 많더라고요.. 팩토리얼(!)만 봐도 애써 시선을 다른 곳으로 돌리던 저에게.. 난항이 예상됩니다…
글 내용이 대부분 다른 블로그의 글을 읽으며 공부하고 정리한 내용이다보니,
참고한 글의 링크를 먼저 알려드릴게요.
1. https://xxxelppa.tistory.com/42
2. https://blog.naver.com/demonic3540/221229805234
3. https://debugdaldal.tistory.com/158
4. https://madplay.github.io/post/time-complexity-space-complexity
아마도 작성된 알고리즘을 분석하기 위한 다양한 복잡도가 있는 것 같아요. 그리고 그 중에서 알고리즘의 성능을 측정하기 위해 ‘시간 복잡도’와 ‘공간 복잡도’를 주로 사용하는 것 같습니다. (그리고 그냥 복잡도라고 말하면 보통은 ‘시간 복잡도’를 말하는 것 같아요.)
여기에서 ‘시간 복잡도’란 알고리즘을 실행하여 종료할때까지 필요한 시간을 말하며(정확하게는 연산 횟수를 말하는 것 같습니다), ‘공간 복잡도’란 알고리즘이 실행되고 종료될때까지 필요한 기억장치의 크기를 말한답니다(여기서 기억장치는 메모리(RAM))
처음에는 시간 복잡도, 공간 복잡도, 빅오 표기법을 한번에 공부해서 적으려 했으나.. 현재의 수준을 감안하여.. 하나씩 하나씩..
앞서 살짝 이야기한대로 시간 복잡도란 알고리즘이 수행되는데 소요되는 연산 횟수를 이야기합니다. 그런데 이 연산 횟수라는게 항상 일정하지가 않아요. 예를 들면 아래와 같은 간단한 예를 보면,
|
1 2 3 4 5 |
function sample(arr, no) { for(let i=0; i<arr.length; i++) { if(arr[i] === no) return i; } } |
여기서 arr 값이 [1, 2, 3, 4, … 10] 이라고 가정을 했을때, no 값이 1이라면 연산 횟수는 1이 되겠지요? 하지만 no 값이 arr의 마지막 값이라면 연산 횟수는 10이 될거에요. 그래서 알고리즘을 평가할때 최선의 경우(Best Case), 평균적인 경우(Average Case), 최악의 경우(Worst Case)로 나눈다고 합니다. 위 예의 경우에 최선의 경우는 1, 최악의 경우는 10, 평균의 경우는 5쯤.. 되겠죠…?
그러면 평균적인 경우의 값이 가장 의미가 있어 보이지만, 알고리즘이 복잡해질 수록 평균값을 계산하기가 어려워지기 때문에 일반적으로 시간 복잡도는 최악의 경우를 많이 사용한다고 합니다.
그리하여 위 예제의 경우의 시간 복잡도는 2n+1이 되는 데요. 아래에서 살펴보면,
(여기서 n = arr.length)
|
1 2 3 4 5 |
function sample(arr, no) { for(let i=0; i<arr.length; i++) { // n + 1 (여기서 + 1은 let i = 1; 을 1번 실행하기 때문입니다.) if(arr[i] === no) return i; // n (반복문이 n번 실행되니 여기도 n번 실행되겠죠?) } } |
위와 같이 총 반복수를 더하면, 시간 복잡도가 2n+1이 됩니다. 그런데 아직 알아보지 않았지만 빅오 표기법으로 표현하면 n의 최고차항만 만겨서 표기하는데요. 왜냐면 n이 엄청 커지면 n+1 같은 건 별로 차이가 없기 때문인데요. 그래서 빅오 표기법으로 표현하면 위 코드의 시간 복잡도는 O(n)이 됩니다.
뜬금없지만… 저와 같은 알고리즘 초보이며, 알고 있는 수학이 산수와 크게 다르지 않다면… 우리는 잠들어 있던 지난 기억을 되살려야 합니다. 우연히 찾았는데 이곳에 수학에 대한 설명이 잘되어 있는거 같아요.
https://mathbang.net/595
(a > 0, a ≠ 1, x > 0)
아주 간단하게 ax = b 라는 식이 있다면 이것은 바로 x = logab 라는 것,
그리고 상용로그라 하여 밑이 생략되어 있는 건 밑이 10이라는 뜻입니다. log10N = logN.
일단은 이 정도만 기억을 소생 시키고 다시 시간복잡도로 돌아갑니다.
이어서 간단한 몇가지 시간 복잡도를 조금 더 살펴보면,
|
1 2 3 4 5 6 7 |
for(let i=1; i<=n; i *= 2) { // code } for(let i=n; i>=1; i /= 2) { // code } |
위 루프의 경우에는 i가 1, 2, 4, 8, 16.. 이렇게 제곱으로 증가하거나 감소합니다. 그렇기에 시간복잡도는 log2n 이 됩니다. (정확하게는 log2n + 1이 겠네요? 그리고 빅오 표기법으로 O(logn))
|
1 2 3 4 5 |
for(let i=1; i<=n; i++) { // N + 1 for(let j=1; j<=n; j++) { // N * (N + 1) // code } } |
위 코드의 경우에는 n번 반복하는 반복문이 두번 중첩되었네요. 그렇기에 시간 복잡도는 n2가 됩니다.
(역시 정확하게는 n2 + 2n + 1 일 것 같아요, 그리고 빅오 표기법으로 O(n2))
|
1 2 3 4 5 |
for(let i=1; i<=n; i++) { for(let j=1; j<=i; j++) { // code } } |
(변수 초기화에 대한 실행은 제외하고) 바깥 반복문은 n번 반복하고, 안쪽은 (n+1)/2번 반복하니까, 위 루프의 시간 복잡도는 n * (n+1)/2 입니다. (빅오 표기법으로 O(n2))
음… (n+1)/2… 잘 생각해보면… (n+1)/2
저와 같이.. 한번에 팍 이해가 안되는 분들을 위해 직접 확인을 해보면,
|
1 2 3 4 5 6 7 |
// 1번 let n = 3; for(let i=1; i<=n; i++) { for(let j=1; j<=n; j++ ) { console.log('n'); } } |
|
1 2 3 4 5 6 7 |
// 2번 let n = 3; for(let i=1; i<=n; i++) { for(let j=1; j<=i; j++) { console.log('n'); } } |
1번의 경우 n은 9번 출력되고 2번은 n이 6번 출력될거에요. 그런데 지금은 안쪽 루프가 몇번 돌았는지 알아야 하니까 바깥 루프가 반복한 3번을 나눠주면, 1번의 경우에는 3번 반복한거고 2번의 경우에는 2번 반복한것이 되는것이죠?
n = 3 라고 가정했으니 1번의 경우 시간 복잡도가 n2 라고 했으니 33 = 9
2번의 경우 시간 복잡도가 n * (n + 1) / 2 라고 했으니 3 * (3+1)/2 = 6
수학적 감각이 부족해서 그런지 딱 보고는 모르겠네요… ㅎ
|
1 2 3 4 5 |
for(let i=1; i<=n; i++) { for(let j=1; j<=n; j *= 2) { // code } } |
(변수 초기화에 대한 실행은 제외하고) 요것은 이제 딱 보면 바깥 루프는 n번 반복하고 안쪽은 log2n번 반복하니까, 시간 복잡도는 n * log2n 이 겠군요! 빅오 표기법으로는… O(nlogn)…?
