2.7 알고리즘1

알고리즘

어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것

시간복잡도

-> 시간이 얼마나 걸리는 지 알 수 있다.

Big O 표기법 주로 사용

• 입력 크기 N에 대해 최악의 경우 얼마나 걸릴지를 알 수 있다.

ex. 1+ ... + n까지 합

1) 시간복잡도 O(n)

//1부터 n까지 실행
	let sum = 0;
	for (let i = 1; i <= n; i++) {
		sum += i;
	}

2) 시간복잡도 O(1)

//한번 실행
	let sum = n * (n+1) / 2

3) O(n^2)

//n제곱번 실행
	let sum = 0;
	for (let i = 1; i <= n; i++) {
		for(let j = 1; j <= n; j++){
        	if(i === j) {
            	sum += i
            }
        }
	}

1초가 걸리는 입력 크기

O(N) : 1억
O(NlogN) : 5백만
O(N^2) : 1만
O(N^3) : 500
O(2^N) : 20
O(N!) : 10

Big O
1) 상수는 버린다.
O(2N^2) == O(1/3N^2) == O(N^2)
2) 두 가지 항에 변수가 같으면 큰 항! (변수가 다르면 그대로)
O(N^2 + 2N) == O(N^2)
O(N^2 + 3M)

메모리

배열 크기가 크거나 , 불필요한 공간을 많이 사용하는 경우