1. Big θ notation ← lower bound 와 upper bound 사이의 중간 값. upper bound 와 lower bound 는 trade off 관계이므로 구할 수만 있다면 평균값을 나타내는 세타 노테이션이 가장 베스트다.
2. 그러나 평균의 경우 구하기가 어려우므로 가장 널리 쓰이는 것은 Worst case 이다.
3. Best, Average, Worst case의 예시.

3번의 기댓값의 경우 발생 확률 (1/n) 과 시행 횟수를 곱한 값의 합을 나타낸다.

1. Description 원칙. 1) 상수는 대문자로 쓴다. 2) 변수는 소문자로 쓰고 띄어쓰기는 _ 를 사용한다. 3) 함수는 동사를 사용하여 기능을 표현한다. 4) 사용자 정의 데이터 타입을 정의할 때는 typedef 연산자를 사용한다.

1. 함수의 파라미터에서 구조체를 불러올 경우, 구조체 자체를 복사하는 것이 아니라, 구조체가 할당된 메모리의 첫 주소값을 파라미터로 넣어줌으로써 접근하게 된다. 이것이 파이썬과 C 를 구분 짓는 가장 큰 C 의 특징이다. (포인터)

Lecture 2: Recursion

1. Recursion = 재귀. 즉 자신을 다시 호출함으로써 문제를 풀어내는 함수. 대표적인 예시 = 팩토리얼
2. Recursion 을 할 때는 Stack 을 사용한다고 생각하면 된다. Stack = first in last out. 호출한 함수가 리턴한 값을 스택에 차곡차곡 쌓아두다가 맨 끝값에 도달했을 때 끝값부터 다시 사용해서 원래대로 돌아오는 과정.
3. 그래서 당연한 말이지만 Recursion 에는 call the recursion 하는 부분과 stop the recursion 하는 두 가지 요소가 있어야 함. 만약 stop 이 없다면? 무한히 호출되며 에러가 남.
4. Recursion 을 만드는 원칙 = Divide and conquer 즉 잘게 쪼갠 다음 그 조각들을 하나씩 정복해 나가라는 것.

1. Recursion 은 Iteration 과 헷갈리기 쉬움. 확실한 건, Iteration 의 경우 while, for 문이 있다는 것 그리고 Recursive 는 recursive call 이 있다는 것! 그리고 대부분의 Recursion 은 반복문으로 환원될 수 있음.
2. Recursion 의 장점: 실행하기 쉽다. 단점: 실행 시간이 오래 걸린다. Iteration 은 그 반대가 장단점!
3. 팩토리얼, 제곱, 피보나치 세 케이스에 대해서 반복문과 재귀 호출 중 뭐가 더 나은 선택인지 살펴 보자. 결론은 iteration, recursion, iteration 의 승리!
4. 팩토리얼의 경우 이터레이션으로 할 경우 T(n) = O(n) (n번의 곱하기 연산이 있으니까.) Recursion 으로 할 경우에는 T(n) = T(n-1) + 1 = O(n) (그럼 T(n-1) = n-1 = O(n) 이니까 1은 무시해도 되어서 결과적으로 T(n) = O(n) 이 되는 것인가? ) 결국 시간 복잡도는 같지만, 아까 iteration 이 더 빠르다고 햇으므로 iteration 이 win!