컴퓨터 공학 - 코드 실행 순서, 부동소수점, 정규화, 앱실론, Big O of n 학습

코드 실행 순서

1. 코드 작성 및 실행

1
2
3

int a = 10;
int b = 20;
int c = a + b;

2. RAM에서 a, b 저장

1
2

a = 10
b = 20

3. Register에 EAX, ECX 저장

1
2

EAX = 10
ECX = 20

4. ALU에서 계산

1

10(EAX) + 20(ECX) = 30

5. Register에서 EAX 저장

1

EAX = 30

6. RAM에 c 저장

1

c = 30

참고 : CPU 구성

• ALU(Arithmetic Logic Unit)
• CU(Control Unit, 제어유닛)
• Register(저장)

부동소수점 (floating-point)

• 10.23 × 10^2
  • 10.23 : 가수부(mantissa)
  • 10^2 : 지수부(exponent)

• 1.0101 × 2^4

  • 단정도(single precision)
    • 32bit : 부호(1bit) + 지수(8bit) + 가수(23bit)
      -

  • 배정도(double precision)

    • 64bit : 부호(1bit) + 지수(11bit) + 가수(52bit)

  • 지수부를 높인다는 것 = 표현범위를 넓힌 것

  • 가수부를 높인다는 것 = 정밀도를 높인 것
  • 파이썬 내부는 double precision으로 만들어져 있다.

정규화 (normalization)

• 0이 아닌 자연수 1자리로 만들어라.
  • ex) 5234(10) –> 정규화 –> 5.234 × 10^3
  • ex) 1011(2) –> 정규화 –> 1.011 × 2^3
    • 2진수에서 맨 앞자리는 항상 1이므로, 실제 mantissa에서는 앞의 1을 저장하지 않는다. (±1.man × 2^(exp-bias))
    • bias = 2^(n-1)-1 (n: 지수부가 저장되는 bit 크기)
• 1.0101 × 2^5 (Single precision)
  • exp(실제 저장되는 메모리) - bias(상수) = 5
  • exp = 5 + 2^(8-1)-1 = 132
  • 132(10) –> 10000100(2) –> exp에 저장

앱실론 (epsilon)

• 1.0과 그 다음에 표현할 수 있는 수 사이의 차이

• 어떤 수 다음에 표현할 수 있는 수 사이의 거리(diff)

  • 2^E × epsilon ≒ |num| × epsilon
    • ex) 10.5(10) = 1.0101(2) × 2^3
      • diff = 2^3 × epsilon(2^-23) = 2^-20 ≒ 10.5 × 2^-23

• 실수 비교는 if(a == b) 처럼 직접 비교하면 안된다.

  • a, b 비교 함수를 작성해 비교해야 한다.

Big O of n

• 연산횟수를 나타내는 정도 : O(n)
• O(1) : 상수시간(constant)
  • array : indexing, arr[3]
  • linked list : insert(), delete()
• O(logn)
  • binary search(이진 탐색)
  • BST(이진 탐색 트리)
  • insert
  • search
  • delete
• O(n)
  • array : insert, delete
  • linked list : search
• O(n·logn)
  • quick sort(현업에서 많이 쓰이는 sort)
  • merge sort
  • heap sort
• O(n^2)
  • bubble sort
  • selection sort