알고리즘 특강_3

[ 복잡도 ] 

- 시간 복잡도

: 입력 값과 연산 수행 시간의 상관관계를 나타내는 척도 (= 코드의 시간적 효율성)

 

- 시간 복잡도의 개념 : 코드의 효율성 측정을 위해 실제 실행 시간이 얼마나 걸릴지 표현해 보고 싶다.

 

- 실제의 실행시간에 영향을 주는 여러가지 요인

 -> 컴퓨터의 처리 속도

 -> 사용된 언어

 -> 컴파일러의 속도

 

  => 코드가 단순히 몇 초, 몇 분 만에 실행됬다는 것을 기준으로 성능을 평가하기 어렵다.

 

( 점근적 표기법 )

=> 입력값에 따른 수행 시간의 증가율에 집중하기 위해 중요하지 않은 요소를 제거하는 표기법

function solution(n) {
  let count = 0;

  // 2n²
  // 2n²번 반복
  for (let i = 0; i < 2; i++) {
    // n번 반복       
    for (let i = 0; i < n; i++) {
      // n번 반복
      for (let j = 0; j < n; j++) {
        count++;
        console.log('2n² 반복문', i, j, count);
      }
    }
  }

  // 8n
  // 8번 반복
  for (let i = 0; i < 8; i++) {
    // n번 반복
    for (let j = 0; j < n; j++) {
      count++;
      console.log('8n 반복문',i, j, count);
    }
  }

// 50
// 50번 반복
  for (let i = 0; i < 50; i++) {
    count++;
    console.log('50번 반복문', i, count);
  }

  console.log('total count:', count);
}

solution(3)
solution(20)
solution(100)

// 상수, 낮은 차항, 계수는 무시합니다
2n² + 8n + 50 에서 가장 중요한 요소는 n²입니다

 

- 점근적 표기법의 종류

오메가 표기법	최상의 수행 시간을 표기하는 방법으로 Ω(N) 과 같은 형태로 표현한다.
세타 표기법	평균의 수행 시간을 표기하는 방법으로 Θ(N) 과 같은 형태로 표현한다.
빅오 표기법	최악의 수행 시간을 표기하는 방법으로 O(N) 과 같은 형태로 표현한다.

const arr = [??, ??, ??, ??, ??, ??, ??, ??, ??, ??];

// 최상이라면 한 번에 찾을 수도
// 평균이라면 배열의 중간까지 찾을 수도
// 최악이라면 배열의 끝까지 찾을 수도

 

• 보통 시간 복잡도는 점근적 표기법 중 최악의 경우의 수를 나타내는 Big-O 표기법을 사용
• 최악의 경우가 계산하기 편하면서도, 평균의 수행 시간을 예측하기 쉽기 때문

[ 공간 복잡도 ]

 => 프로그램의 실행에 얼마나 많은공간(메모리)가 필요한지 나타내는 척도 (=공간적 효율성)

function solution(n) {
	return '수박'.repeat(5000).slice(0, n)
}

• 가능하면 적은 메모리를 사용해서 문제를 풀이하도록 하는 것이 좋습니다.
• 보통, 공간복잡도의 경우 제한량이 넉넉하게 주어지므로 크게 걱정하실 필요는 없다.

[ 디버깅 활용 ]

function solution (arr, divisor) {
	debugger
	let answer = []
	
	for (const num of arr) { 
		if(num % divisor === 0) answer.push(num)
	}
	
	answer.sort((a,b) => a - b)
	
	if(answer.length === 0) answer.push(-1)

  return answer
}

const arr =[10, 5, 9, 7]
const divisor = 5

solution(arr, divisor)