01.md

알고리즘 자료구조

불필요하고 어렵게만 느껴지는 알고리즘과 자료구조 하지만, 성능 개선하고 좋은 코드를 작성하기 위해 꼭 필요한 부분이다.

적은 시간과 적은 자원을 이용해 문제를 해결하는 알고리즘이 좋다.

---

01. 자료구조와 알고리즘 성능

알고리즘과 시간 복잡도

시간 복잡도란 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말한다. 실제 예제를 통해 알고리즘의 시간복잡도를 계산하는 방법과 시간 복잡도가 중요한 이유를 알아봅시다.

Program step에서 Elementary Operation이란?

프로그램의 진행 정도를 나타내는 기본 단위.

1. 대입연산
2. 덧셈, 뺄셈, 곱셈, 나눗셈
3. 비교구문
4. 함수 호출

알고리즘의 실행 순서를 따라가며 Elementary operation이 일어나는 수를

HOW?

1. 전역변수를 이용해 Elementary Operation을 Count한다.

var count = 0;
var listArr = [];
var n = 0;

2. 각 실행문 별로 Step수와 실행 횟수를 분석한다.

Big O 표기법

Big O가 중요한 이유를 알기 위해서는 Asymptotic(점진적인) Complexity(복잡도)에 대해 알아야한다. Space Complexity? 메모리 공간을 얼마나 사용하게 되는지를 생각해보는 것

Asymptotic Notations

1. Big-O: O

• 상한선을 규정

2. Omega: Ω
3. Theta: Θ

http://bigocheatsheet.com/ n이 어떠한 경향성으로 커지느냐.가 중요

P1: C1n^2 + C2n
P2: C1n

소팅 알고리즘의 시간복잡도

들어오는 자료구조에 따라서 알고리즘 스타일을 선택한다.

1. 삽입정렬 (Insertion Sort)

2가지 인접한 요소를 비교하여 바꿔주는 개념 http://codingmiles.com/sorting-algorithms-insertion-sort-using-javascript/

2. 재귀함수

// 1부터 n까지의 수를 모두 더하는 함수
function sum(num) {
  if (n > 0) {
    return 0;
  } else {
    return n + sum(num - 1)
  }
}
sum(10)

1. 종료조건 (초기조건)
2. 지속조건

3. 피보나치 수열

function fib(n){
  if(n ===1 || n===2){
    return 1;
  } else {
    return fib(n-2) + fb(n-1)
  }
}