알고리즘 - ( 코드 최적화하기 - 빅오표기법 이용 )

최적화의 첫번째 단계

• 코드의 효율성을 알아내는것

문제별 코드 최적화

짝수의 평균

function average_of_even_numbers(array){
	let sum = 0;
	count = 0;
	
	for(let i=0; i<array.length; i++){
		if(array[i]%2 === 0){
			sum+=array[i];
			count +=1;
		}
	}
	return sum / count;
}

기본적으로 루프는 원소 N개를 순회하니 알고리즘에서는 최소 N단계가 걸린다.
그리고 만약 짝수일 경우, 비교, sum, count 총 3단계를 더 수행한다.

최악의 경우, array 즉 N이 모두 짝수일 경우, 3N 이 되게 된다.

여기서 sum과 count를 초기화 시켜주는 것 2단계, return 결과값 까지 하면 총 단계수는 3N+3이된다.

단어생성기 (문자배열로부터 두 글자짜리 모든 문자열 조합)

ex) [”a”,”b”,”c”,”d”] → [”ab”,”ac”,”ad”,…….]

function wordBuilder(array){
	let collection = [];
	
	for(let i=0; i<array.length; i++){
		for(let j=0; i<array.length; j++){
			if(array[i]!==array[j]){
				collection.push(array[i]+array[j]);
			}
		}
	}
	return collection;
}

바깥루프는 N개 원소를 모두 순회하고 각 원소마다 안쪽 루프는 다시 N개 원소를 모두 순회하니 N단계에 N단계를 곱한 것과 같다. O(n^2)

배열예제

function sample(array){
	const first = array[0];
	const middle = array[int(array.length/2)];
	const last = array[-1];

	return [first, middle, last];
}

N이 얼마든 걸리는 단계수가 동일하다. 배열의 시작과, 중간, 마지막 인덱스 읽기는 배열 크기에 상관없이 딱 한 단계이다. ⇒ O(1)

평균 섭씨 온도 구하기

function average_celsius(fahrenheit_readings){
	let celsius_numbers=[];
	
	for(let i=0; i<fahrenheit_readings.length; i++){
		celsius_conversion = (fahrenheit_readings[i] - 32) / 1.8;
		celsius_numbers.push(celsius_conversion);
	}
	
	let sum = 0;
	
	for(let j=0; j<celsius_numbers.length; j++){
		sum += celsius_numbers[j]
	}
	
	return sum / celsius_numbers.length
}

여기서 루프 2개를 실행한다.
루프 두개에서 원소 N개를 전부 순회하니 N+N, 즉, 2N이 걸린다. ⇒ O(N)

의류 상표

function mark_inventory(clothing_items){
	let clothing_options =[];
	
	for (let i=0; i<clothing_items.length; i++){
		for(let j=0; j<5; j++){
			clothing_options.push(`${clothing_items[i]} Size : ${j+1}`)
		}
	}
	
	return clothing_options
}

중첩 루프가 O(N^2)이 되는 경우는 각 루프에서 N개씩 처리할 때다. 하지만 여기서 바깥 루프가 N번 실행되는 동안 안쪽 루프가 5번 실행된다.

5N ⇒ O(N)

1 숫자 세기

배열안에 배열이 존재하는데, 그 배열에는 1,0으로 이루어져있다. 배열들에 들어 있는 1의 개수를 반환한다.

function count_ones(outer_array){
	let count = 0;
	
	for(let i=0; i<outer_array.length; i++){
		for(let j=0; j<outer_array[i].length; j++){
			if(outer_array[i][j]===1) count+=1;
		}
	}
	return count;
}

중첩루프라 O(N^2)으로 오해하기 쉽다. 하지만 루프 2개가 완전히 다른 배열을 순회한다. 바깥 루프는 안쪽 배열을 순회하고, 안쪽 배열은 실제 내부에 담겨져있는 수를 순회한다. 결국 안쪽 루프가 총 수개수만큼 실행된다.

ex) [[1,0,1,0,0],[1,1,1,0,0,1],[0,0,1,0,1,1,1]]

따라서 N은 수의 개수이다. 시간복잡도 : O(N)

모든 곱 구하기

[1,2,3,4,5] ⇒ [2,3,4,5,6,8,10,12,15,20]

function twoNumberProducts(array){
	let products=[];
	
	for(let i=0; i<array.length-1; i++){
		for(let j=i+1; j<array.length; j++ ){
			products.push(array[i]*array[j]);
		}
	}
	return products;
}

가령 2를 나머지 수들과 곱할 때 오른쪽에 있는 수만 곱한다. 앞서 1을 2와 곱했으므로 다시 뒤로 돌아가 2를 1과 곱하지 않아도 된다. 따라서 각 수는 오른쪽에 남아 있는 수만 곱해야한다.

→ 바깥 루프는 N 번 실행되며, 안쪽 루프는 바깥루프를 한번씩 돌때마다 1씩 줄어든다.

N+(N-1)+(N-2)+….+1 ⇒ (N^2)/2

안쪽 루프는 (N^2)/2 단계를 실행한다. 시간복잡도 : O(N^2)

배열 x 배열 크기에 따른 시간 복잡도

브루토 포스 방식 : 하나하나 다 대입해오는 방식

시간복잡도 : O(2^N)

O(N^3)보다 훨씬 느리다.

O(2^N)은 O(logN)의 반대다. (이진검색) O(logN)인 알고리즘에서는 데이터가 2배로 늘어날 때 알고리즘에 한 단계씩 더 걸린다.
O(2^N)알고리즘에서는 데이터가 하나 늘어날 때 알고리즘에 필요한 단계가 2배 늘어난다.