알고리즘 .2

시간복잡도 공부..!!

프로그램의 수행성능을 최악의 경우를 가정하여 정량화 하는 방법이라고 하는데 그냥 쉽게 얘기 하자면 

최악의 경우를 계산하여야 한다 !! 이 정도로 보아야 할듯

// 사례
function find_max_num(array) {
    for (let num of array) {
        let isMax = true;
        for (let compare_num of array) {
            if (num < compare_num) {
                isMax = false;
                break;
            }
        }
        if (isMax) {
            return num;
        }
    }
}

console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]));
console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]));
console.log("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]));




// 시간 복잡도로 계산한 코드
for (let num of array) { // array 의 길이만큼 아래 연산이 실행
		let isMax = true;
		for (let compare_num of array) { // array 의 길이만큼 아래 연산이 실행
				if (num < compare_num) { // 비교 연산 1번 실행
						isMax = false;
						break;
        }
    }
		if (isMax) {
				return num;
		}
}

어음.. 이게 무슨 말인교...?ㅋㅋㅋㅋ

예시와 답안을 복붙 하였는데 솔직히 무슨 소리인지 1도 모르겠다;;

 

일단 다시 한번 확인하자면 문제를 해결하는데 걸리는 시간과 입력의 함수관계를 잘 파악해야 한다 

실행시간을 알아보자면 array의 원소 개수와 X array의 원소 개수만큼 비교 연산 하는 것 !!

그렇게 되면 이 함수의 N2만큼의 시간을 알 수 있게된다.

 

즉 시간 복잡도는 Big-O(빅오) 표기법으로 표시하며 이 경우엔 O(N2)의 시간 복잡도를 가진다고 한다.

 

공간 복잡도...??

공간 복잡도는 시간 복잡도와 다르게 문제를 해결하는데에 대한 공간과의 상관관계를 말하는것이란다..

쉽게 얘기 하자면 N개의 입력이 주어지면 얼마의 공간을 쓰는지 나타내는 것...!!

function largest_product(my_list) {
    let products = [];
    for (let a of my_list) {
        for (let b of my_list) {
            // products 배열에 원소가 들어가는 이 연산은 (a * b)번이 실행될것 2중 루프!
            products.push(a * b);
        }
    }
    // 따라서, products의 공간 복잡도는 O(N^2)
    return Math.max(...products);
}

let myList = [1, 3, 5, 7, 9];
console.log(largest_product(myList));

공간 복잡도를 사용하는데에 있어 중요한 것은 지나치게 공간을 낭비하는 것을 주의 해야 한다는 것...!!

단, 현업에 있어 알고리즘의 성능 향상을 하기 위해선 공간을 필수적으로 더 사용해야 한다면 더 쓰는걸 추천..!!

 

여기까지가 시간복잡도, 공간복잡도의 기본적인 내용인데 솔직히 많이 어렵다..ㅋㅋ

 

요새 개인과제를 받고 개인과제 준비중이라 조금 바빠서 그런지 모든 일에 조금 우선순위를 두기 시작했다ㅜㅠ

그래서 알고리즘은 살짝.. 뒤로... 하지만 !! 하루에 최소 한번씩 알고리즘 공부가 필요하다는 것을 이번 알고리즘 강의를 듣고 느끼는중..

 

현재 공부상황은 인강은 다 듣고 개인적으로 코드 짜는 능력이나 코드를 읽는 능력이 부족하다는걸 느껴 프로그래머스나 개인적으로 코드를 만들어 보는중..

거기에 대비해 개인과제는 어제 완성이 되었는데 오늘 조원분들이나 대표로 설명하셨던 분의 자료와 설명을 듣고 몇가지 기능을 추가하고 주석을 달고 마무리 작업까지 끝냈다는...!! ㅋㅋㅋ

 

다행스럽게 그전에 있던 조원분들 조언이나 현 조원분들의 조언등을 토대로 하여 개인과제 코드를 짜 맞추었는데

그래서 그런지 내가 코드를 만들었지만 상대에게 설명하는것에 있어 매우 부족한것 같다..

 

내가 짠 코드를 제대로 설명 못한다는건 매우 불쾌한 기분이 드는데 어떤식으로 개선해야 할 지 요새 조금 고민이 든다...!!

 

여튼~ 알고리즘 공부라고 적고 푸념을 늘어놨다는;;