복잡도 | 비트 | Byte Padding 정리

Big-O

• 복잡도의 점근적 상한 표기

  가장 느리면 이 정도 걸린다

Big-Omega

• 복잡도의 점근적 하한 표기

  최소한 이 시간만큼은 걸린다

 

Big-Theta

빅오와 빅오메가가 같을때 표기

 

f(n) = 2n^2 + 8n + 3 = O(n^2) = C(n^2)

f(n) = Theta(n^2)

 

f(n)은 n이 증가함에 따라 n^2과 동일한 증가율을 가진다 라는 의미

 

---

 

비트연산

 

프로세스 성능 향상 위해 => 주소버스가 4의 배수형태의 주소만 허용

 

어떤 객체(byte)가 4의 배수형 주소에 있지 않다면

메모리 접근을 2번 해야 한다.

 

변수 별 메모리 주소 번지 패턴

• 1byte 형 : 모든 주소 번지에 기록 가능
• 2byte 형 : 2byte boundary에 정렬
• 4byte 형 : 4byte boundary에 정렬
• Double 형 : windows에선 8byte, 리눅스에선 4byte boundary

 

 

구조체 Byte Padding

• 구조체의 멤버들 사이에 임의 공간 생기는 현상.
• 구조체는 가장 큰 데이터타입 배수 값으로 크기 결정되므로

struct Message{
    char Data1;     
    short Data2;
    int Data3;
    char Data4;
} m;

Data1		Data2	Data2
Data3	Data3	Data3	Data3
Data4

구조체 크기가 4바이트 추가됨을 알 수 있다

이를 Padding byte라 부른다.

 

구조체 멤버들 순서를 잘 배치하면 필요 메모리 크기 DOWN

xxxxxxxxxx
struct Message{
    char Data1;
    short Data2;
    int Data3;
    char Data4;
} m;

 

Data1		Data2	Data2
Data3	Data3	Data3	data3
Data4

 

구조체 선언되는 순서에 의해 Padding Byte 결정

 

---

 

 

완전검색

문제의 해를 찾기 위해 가능한 모든 경우를 나열해보고 확인하는 기법.

빠른 시간에 해를 구하는 것은 아니다

 

입력의 크기가 작은 경우의 알고리즘 설계

1. 그리디 기법
2. 동적계획법