백투더코딩

Big O 시간의 상한(최악)

g(n)<=c*f(n):asymptotic upper bound

(c:some positive real constant N:some nonnegative integer s.t. for all n>=N)

g(n) is big O of f(n)

Omega 시간의 하한(최선)

g(n)>=c*f(n):asymptotic lower bound

(c:some positive real constant N:some nonnegative integer s.t. for all n>=N)

g(n) is omega of f(n)

Order 시간의 평균

c*f(n)<=g(n)<=d*f(n)

(c,d:some positive real constant N:some nonnegative integer s.t. for all n>=N)

g(n) is order of f(n)

오더를 빅오로 사용하는 경우가 많습니다.

참고 사이트

https://memostack.tistory.com/57

-fixed part 

instruction space

simple variable ex) x=3;

const

fixed size variables ex) a[10]

-variable part

variables depending on input

ex)s[n]

recursion stack

Space complexicty:memory

Time complexity:execution time

Algorithm's efficiency:#of basic operations executed as a function of input size

Basic operation

-single or group instructions

-execution time is independent of n

n:input size

Input size

-배열의 키들의 갯수

->sequential search, binary search, add array members, exchange sort

-#of rows and columns

->Matrix multiplication

-#of nodes and edges

->graph:n,e n-1<=e<=n(n-1)/2

-logn(floor처리)+1

->피보나치

#:number

L1 물리계층

주소 개념 없고 비트0,1

L2 데이터링크계층

물리 네트워크 이용해서 패킷 전달, frame 단위

이질성이 높음

유선 LAN, 무선 LAN, 유선 WAN등이 있음

국가 ISP=backbone=core

H: host

R:라우터

S:소스

D:데스티네이션

L3 네트워크 //논리주소=프로토콜주소=네트워크주소=ip주소 //ICMP,IP,ARP 

IP주소와 RoutingTable을 활용해 패킷을 송신자 노드에서 수신자 노드까지 전달함

host-to-host delivery

표준기관들에 따라 정해짐

IANA->APNIC(전세계 중 일부 지역)->KISA(한국) 국제기관에서 국내기관으로 점점 좁아지며 세분화된다.

blog.ac.kr이라는 주소가 있다고 가정해보자

여기서 kr을 TLD(top level domain)이라고 하는데

com.org는 gTLD(generic~~)

kr,us는 ccTLD(countrycode~~)이다. 

KISA에서는 한국 IP주소와 DomainName을 정해주는데

co, or, ac 등이 그 예이다. 

blog.ac.kr