O(빅오) , 메모리계층

linear search의 t(n)이 = n이 되는 이유는 각각 비교하기 때문에.

binary search의 t(n)이 되는 이유는, 한번 줄어들때마다 1/2씩 감소하므로 (1/2)^k * n = 1

log2^2^-k = log2 n^-1

k * log2^2 =log 2*n

k= log2n

오메가() lower-bound (하한선)
세타() opper-bound + lower-bound
빅오() upper -bound

0(1) :상수시간 연결리스트의 삽입,삭제 배열의 indexing arr[2]

O(log n) :로그시간 bst

O(n) : 선형시간 연결리스트의 탐색, 어떤 배열의 삽입,삭제 -> comparison sorting 아무리 좋아도 비교정렬중에 이보다 좋을수는없다

O(n log n) : 선형로그시간 퀵소트, 머지소트

O(n^2) 지수 시간 버블소트,선택정렬, 삽입정렬

이중 3층인 메모리층에는
code
data
heap
stack이 존재해서, heap 영역은 내려가고 stack은 올라간다. heap은 느리고 stack은 빠르다

cache의 존재이유는 principle of locality -시간지역성, 공간지역성
locality를 만족하면 cache hit/ 만족못하면 cache miss가 발생한다

ㅡ> L1 CASHE miss의 가상메모리 한단계이다.