[Data Structures] 자료구조와 알고리즘에 대한 기본 이해

1. 자료구조 vs 알고리즘

자료구조: 데이터의 표현 및 저장방법

알고리즘: 표현 및 저장된 데이터를 대상으로 하는 '문제의 해결 방법'

 

 

 

2. 자료구조의 분류

출처: https://pccoms.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

 

 

 

3. 시간 복잡도 (Time Complexity) & 공간 복잡도 (Space Complexity)

시간 복잡도: 알고리즘의 속도를 평가하는 요소

                 연산의 횟수를 통해서 빠르기 판단 / 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성

공간 복잡도: 알고리즘의 메모리 사용량을 평가하는 요소

 

 

 

4. 순차 탐색 알고리즘 (Linear Search Algorithm)의 시간 복잡도 계산

• if(ar[i] == target)  핵심이 되는 연산을 중심으로 시간 복잡도를 계산
• Worst Case를 중심으로 알고리즘의 성능을 판단
• 데이터가 n개라고 가정하면 == 비교연산을 총 n번 진행하므로        T(n) = n

#include <stdio.h>
 
int BSearch(int ar[], int len, int target)
{
    int first = 0;
    int last = len-1;
    int mid;    
 
    while(first<=last)
    {
        mid = (first+last)/2;
        if(ar[mid]==target){
            return mid;
       }
        else{
            if(ar[mid] > target)
                last = mid-1;
            else 
                first = mid+1;
        }
    }
    return -1;
}
 
int main(void)
{
    int arr[] = {1,3,5,7,9};
    int idx;
    
    idx = BSearch(arr, sizeof(arr)/sizeof(int), 7)
    if(idx == -1)
        printf("Failed to search\n");
    else
        printf("Target Index: %d\n", idx);
 
    idx = BSearch(arr, sizeof(arr)/sizeof(int), 4)
    if(idx == -1)
        printf("Failed to search\n");
    else
        printf("Target Index: %d\n", idx);
 
    return 0;
}