[Data Structure] 1.

ref : 윤성우의 자료구조

자료구조란?

• 자료구조는 데이터를 표현하고 저장하는 방법이다.
• 알고리즘은 문제해결방법이다.

복잡도

• 시간복잡도 : 알고리즘의 수행시간
• 공간복잡도 : 메모리의 사용량

선형구조 vs 비선형구조

• 선형구조

  • list
  • queue
  • stack

• 비선형구조

  • tree
  • graph

시간복잡도 O(f(n)) 이 의미하는 바.

두 개의 함수 f(n) 과  g(n) 이 주어졌을 때, 모든 n >= K (K 는 큰 수) 대하여 f(n) <= C(g(n)) 을 만족하는 두 개의 상수 C 와 K가 존재한다면, f(n) 의 빅 오는 O(g(n)) 이다. (여기서 K 와 C 은 매우 큰 수)

이 말이 의미하는 바는, f(n) 이 아무리 커진다해도, Cg(n)을 넘지 못한다는 못한다는 말 (예를 들어, f(n) = 3n^2 + 2n 이고, g(n) = n^2 이면, f(n) 이 아무리 커져도 n^2 의 증가율은 넘지 못한다는 뜻이다.

탐색 알고리즘 연산의 핵심은 "==" 이다. 시간복잡도 : O(n)

순차탐색 알고리즘 (linear search)

//Linear Search
//주목할 점은 sizeof 를 사용해서 len 를 구한다

#include <stdio.h>

int linear_search(int [], int , int);

int main(int argc, const char * argv[]) {
    
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    
    int result = linear_search(arr, sizeof(arr)/sizeof(int), 5);
    
    if(result == 1) printf("found\n");
    else printf("no found\n");

    return 0;
}


int linear_search(int arr[], int len, int val){
    for(int i = 0 ; i < len; i++){
        if(arr[i] == val) return 1;
    }
    return -1;
}

이진 탐색 알고리즘 (binary search) 시간 복잡도 O(logn)

int binary_search(int[], int, int);


int main(int argc, const char * argv[]) {
    
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    
    //int result = linear_search(arr, sizeof(arr)/sizeof(int), 5);
    int result = binary_search(arr, sizeof(arr)/sizeof(int), 10);
    
    if(result == 1) printf("found\n");
    else printf("no found\n");

    return 0;
}

int binary_search(int arr[], int len, int val){
    
    int first = 0;
    int last = len - 1;
    int mid;
    while(first <= last){
        mid = (first + last) / 2;
        if(arr[mid] == val) return 1;
        if(arr[mid] > val) first = mid + 1;
        else last = mid - 1;
    }
    return -1;
}