[자료구조] 1. 자료구조와 알고리즘

1.1 자료구조와 알고리즘

▶ 알고리즘의 조건

• 입력: 0개 이상의 입력
• 출력: 1개 이상의 출력
• 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.
• 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다. (예외: 운영체제)
• 유효성: 각 명령어들이 실행 가능한 연산이어야 한다.

 

▶ Property of Algorithm

• Corectness: 알고리즘이 해결하고자 하는 목표에 얼마나 근접했는지 (error rate)
• Precision: 서로 다른 input에도 유사한 corectness이면, precision이 높다.
• Determinism: 동일한 input에도 서로 다른 결과이면, determinism이 낮다.

 

▶ 32-bit OS vs. 64-bit OS

• 32-bit OS: 메모리 주소 단위가 32-bit(4 bytes)이므로, (2^32-1) bytes 메모리 사용 가능; 주소를 32-bit로 표현한다.
• 64-bit OS: 메모리 주소 단위가 64-bit(8 bytes)이므로, (2^64-1) bytes 메모리 사용 가능; 주소를 64-bit로 표현한다.

 

▶ Data types

• bool, char: 1B
• short: 2B
• int, float: 4B
• double: 8B
• long: 4B(32-bit OS), 8B(64-bit OS)
• pointer: 4B(32-bit OS), 8B(64-bit OS) --> dynamic memory allocation during runtime
  cf) Array --> static memory allocation, fixed size of memory

 

▶ struct(구조체) vs. union(공용체) vs. enum

struct(구조체) vs. union(공용체

• struct: 변수들이 각각의 고정된 메모리에 할당되어, 각 element들이 독립된 메모리를 사용한다.
• union: 변수들 중 가장 큰 것의 크기만큼만 메모리가 할당되고, 공유해서 사용한다.

 

 

1.2 추상자료형(ADT; Abstract Data Type)

: information hiding

 

 

1.3 알고리즘의 성능 분석

▶ 수행 시간 측정 방법

 

▶ 알고리즘의 복잡도 분석 방법: Big O()

• O(1) < O(loglogn) < O(logn), O(root(n)) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) <O(n^n)

 

---