데이터 구조 및 알고리즘

*

데이터 구조란?

데이터 구조는 데이터를 효율적으로 사용할 수 있도록 데이터를 저장하는 프로그래밍 방식입니다.

알고리즘이란?

유한한 순서의 명령, 각각
명확한 의미를 가지고 있으며 유한한 시간 동안 유한한 노력으로 수행할 수 있습니다.

데이터 구조 및 알고리즘의 응용

데이터 구조 관점에서 다음은 몇 가지 중요한 알고리즘 범주입니다.

검색 - 데이터 구조에서 항목을 검색하는 알고리즘입니다.

정렬 - 특정 순서로 항목을 정렬하는 알고리즘입니다.

삽입 - 데이터 구조에 항목을 삽입하는 알고리즘.

업데이트 - 데이터의 기존 항목을 업데이트하는 알고리즘
구조.

삭제 - 데이터에서 기존 항목을 삭제하는 알고리즘
구조.

알고리즘의 특성

Unambiguous − 알고리즘은 명확하고 모호하지 않아야 합니다.
각 단계(또는 위상) 및 입력/출력
명확해야 하며 단 하나의 의미로 이어져야 합니다.

입력 − 알고리즘은 0개 이상의 잘 정의된
입력.

출력 − 알고리즘은 하나 이상의 잘 정의된
출력하고 원하는 출력과 일치해야 합니다.

Finiteness − 알고리즘은 유한한 시간 후에 종료되어야 합니다.
단계 수.

타당성 - 사용 가능한
자원.

Independent − 알고리즘은 단계별
모든 프로그래밍과 독립적이어야 하는 방향
암호.

알고리즘은 실행하는 데 시간이 덜 걸리고 메모리 공간을 적게 사용하는 경우 효율적이고 빠릅니다. 알고리즘의 성능은 다음 속성을 기반으로 측정됩니다.

시간 복잡도

공간 복잡성

시간과 공간 측면에서 알고리즘의 복잡성을 분석할 때 필요한 시간과 알고리즘에 필요한 공간을 정의하는 정확한 숫자를 제공할 수 없으며 대신 점근적 표기법이라고도 하는 표준 표기법을 사용하여 표현합니다. .

알고리즘의 공간 복잡성

공간 복잡성은 결과를 실행하고 생성하기 위해 알고리즘(알고리즘에 대한 입력 값 포함)에서 사용하는 메모리의 양입니다.

공간 복잡도 계산

공간 복잡도를 계산하는 동안 다양한 유형의 데이터 유형 변수가 사용하는 메모리 값을 알아야 합니다.


유형
크기


부울, 문자, 부호 없는 문자, 부호 있는 문자, __int8
1바이트

__int16, 짧은, 부호 없는 짧은, wchar_t, __wchar_t
2바이트

float, __int32, int, unsigned int, long, unsigned long
4 바이트

더블, __int64, 롱 더블, 롱 롱
8바이트


예 1:

{
    int x = a + b ;
    return(x);
}

위의 예에서 변수 x, a 및 b는 모두 정수 유형이며 각각 4바이트를 차지하므로 총 메모리 요구 사항은 (3(4) +4 = 20바이트이며 이 추가 4바이트는 반환용입니다. 그리고 이 공간 요구 사항은 위의 예에서 고정되어 있으므로 이를 Constant Space Complexity라고 합니다.

예 2:

// n is the length of array a[]
int division(int a[], int n)
{
    int x = 0;      // 4 bytes for x
    for(int i = 0; i < n; i++)  // 4 bytes for i
    {   
        x  = x / a[i];      
    }
    return(x);
}

위의 코드에서 배열 a[] 요소에는 4*n 바이트의 공간이 필요합니다.

x, n, i 및 반환 값에 대해 각각 4바이트.
따라서 총 메모리 요구 사항은 (4n + 12)이며 입력 값 n이 증가함에 따라 선형적으로 증가하므로 선형 공간 복잡도라고 합니다.

알고리즘의 시간 복잡도

프로그램을 사용하여 해결해야 하는 모든 정의된 문제에 대해 무한한 수의 솔루션이 있을 수 있습니다.

알고리즘의 시간 복잡도는 프로그램이 완료될 때까지 실행하는 데 필요한 총 시간을 나타냅니다.

알고리즘의 시간 복잡도는 Big O 표기법을 사용하여 가장 일반적으로 표현됩니다. 시간 복잡도를 나타내는 점근적 표기법입니다.
알고리즘의 성능은 입력 데이터의 유형에 따라 다를 수 있으므로 알고리즘의 경우 일반적으로 알고리즘의 최악의 경우 시간 복잡도를 사용합니다. 이는 모든 입력 크기에 대해 소요되는 최대 시간이기 때문입니다.