[C언어로 쉽게 풀어쓴 자료구조] 1장 자료구조와 알고리즘

C언어로 쉽게 풀어쓴 자료구조: 1장 자료구조와 알고리즘

 

1.1 자료구조와 알고리즘

자료구조란?

자료들을 정리하여 보관하는 여러 가지 구조

 

 

알고리즘이란?

문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것

입력	0개 이상의 입력이 존재하여야 한다.
출력	1개 이상의 출력이 존재하여아 한다.
명백성	각 명령어의 의미는 모호하지 않고 명확해야 한다.
유한성	한정된 수의 단계 후에는 반드시 종료되어야 한다.
유효성	각 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 한다.

 

---

1.2 추상 자료형

자료형이란?

데이터의 종류: 정수, 실수, 문자열, 배열, 포인터, 구조체 등

 

 

추상자료형(ADT)이란?

추상정, 수학적으로 자료형을 정의한 것

 

---

1.3 알고리즘의 성능 분석

시간복잡도란?

알고리즘의 수행시간 분석

※시간 복잡도에서 상수값은 무시한다.

void f(int n) {     for(int i = 0; i < n; i ++){    ->n        ~~~~~     } }	시간 복잡도 O(n) ➡️코드를 n번 반복
void f(int n) {     for(int i = 0; i < n; i ++){      ->n         for(int j = 0; j < n; j ++){  ->n         ~~~~~          }     } }	시간 복잡도 O(n^2) ➡️코드를 n+n번 반복
void f(int n) {     for(int i = 0; i < n; i +=2){  ->n/2        ~~~~~     } }	시간 복잡도 O(n) ➡️코드를 n/2번 반복 ,but 상수값은 무시  ∴1/2n => n
void f(int n) {     for(int i = 0; i < n; i ++){     ->n        if(n%0)                           ->C0         {             continue;                   ->C1         }         ~~~~                             ->C2     } }	시간 복잡도 O(n) ➡️(C0+C1+C2)*n = 3n, but 상수값은 무시  ∴3n => n
void f(int n) {     if(n == 0)                        ->C0         return 0;     f(n / 2)                           ->f(1/2n) }                                          .                                          .                                          .                                          k번 호출                                   ->   f(n) = f(n / 2^k) + kC0     f(k/2) -> n     f(k/4) -> n          .          .          .     ∴n < 2^k <= kn	시간 복잡도 O(log n) ➡️  2^k <= kn     ->  2^k = kn        k = log2(kn)      k = log2(k) + log2(n)     -> 상수값 제외 ∴ log(n)