알고리즘 수업

 

시그마xipi

f(n)은 n^2이다 라고 '일반 함수'처럼 표현함

- overhead instructinos
- control instructions (46P)
- treshhold value, logn과 nx의 교점, 
- 21p차이남
- 59p 1번 설명/ f(n)은 g(n)의 하한선이다
- loga m 와 logb m은 같은 세타 값을 가진다.
- b>a>0 일 때 a^n은 B^n과 같지 않다.

[기대치 계산 표기법]
1. everything case         세타      **공부
2. Average                  스몰오    **공부   
3. Worst(Upper Bound/상한)   빅오 
4. Best(Lowwer Bound/하한)   오메가

----ETC----

- order = 차수
- 특별한 이야기가 없으면 log는 log2임
- 기대치 계산 시험에 나옴
---- 09.21 ----------

- 챕터2(분할 정복)
- 이분탐색, 합병정렬, 
- 병합정렬의 재귀횟수
- w(n) = 2W 등등 이 공이 nlogn이 어떻게 되나

----09.24----------
- pre,post,inorder에 대해서 (시험) / 방문 순서
- pre,post,in fix는 연산자 위치

----09.26--------

Quicksort: 세타 nlogn

 

• Average case: O(nlog⁡n)
• Worst case: O(n2)
• Space complexity: O(log⁡n)

Mergesort세타 nlogn

 

• Best case: O(nlog⁡n)
• Worst case: O(nlog⁡n)
• Space complexity: O(n)

 

bubblesort: n^2

 

• Best case: O(n)
• Worst case: O(n2)
• Space complexity: O(1)

 

68 - 22p차이남
pivot partication 
최적: 반반으로 쪼갤 수 있을 때: logn
최악: 한쪽으로 쏠릴 떄/ 이미정렬되어 있을 때: n-1


n이 작을 때는 bubblesort가 더 빠르지 않나 so, quicksort를 쓰다가 if(n < 4) 일 때 bubble sort 쓴다

 

 

2.6 Arithmetic with Large Integers

큰 숫자(log으로 표현할 수 없는 수)를 계산할 때는
567,123 * 9,432,232
(567x10^3+123) x ( 9423x10^3 + 232) 
이와 같이 계산해라 Like 행렬 계산처럼   ---100p