CS- 3주차

알고리즘은 문제를 해결하기 위해 특정 순서로 제공되는 일련의 지침입니다. 알고리즘은 속도와 차지하는 메모리 양이 다릅니다. 프로그래밍 과정에서 대부분의 알고리즘은 데이터 검색(검색)과 정렬(정렬)을 기반으로 합니다. 데이터 검색 알고리즘에 대해 알아봅시다:

선형 검색(선형 검색)

다음 배열이 주어집니다:

[20, 500, 10, 5, 100, 1, 50]

배열을 시각화하면 다음과 같이 7개의 빨간색 캐비닛이 나란히 있는 것으로 볼 수 있습니다.

이 배열에서 50개의 숫자를 찾아야 합니다. 컴퓨터는 숫자 50을 찾기 위해 각 사물함을 확인해야 합니다. 이 프로세스를 배열 "검색".
에서 특정 숫자, 문자 또는 기타 요소를 검색하는 과정이라고 합니다. 배열을 알고리즘에 전달하고 알고리즘에 찬장을 열고 숫자 50이 있는지 확인하도록 요청할 수 있습니다. 결과적으로 알고리즘은 “예” 또는 “아니요”(참 또는 거짓)

라고 대답합니다.

다음 지침을 사용하여 알고리즘을 구성할 수 있습니다.

Chapdan o‘ngga har bir eshikni tekshirish:
    Agar 50 soni bor bo‘lsa:
        Ha deb qaytaramiz (return true)
Yo‘q deb qaytaramiz (return false)

위의 지침은 사람이 읽을 수 있는 의사 코드이며 컴퓨터에 제공되는 명령을 더 간단하게 표현한 것입니다.

다음 코드를 사용하여 C에서 선형 검색 알고리즘을 구현할 수 있습니다.

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Butun sonlardan iborat massiv berilgan
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};

    // Kiritilgan sonni massivdan qidiramiz
    int n = get_int("Number: ");
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == n)
        {
            printf("Topildi\n");
            return 0;
        }
    }
    printf("Topilmadi\n");
    return 1;
}

여기서는 for 루프를 사용하여 선형 검색을 수행합니다.
return 0은 프로그램이 성공적으로 종료되고 프로그램이 종료되었음을 의미합니다.
return 1 - 프로그램에서 오류가 발생했음을 나타냅니다.

---

바이너리 검색

이진 검색은 숫자 50을 검색하는 데 사용되는 또 다른 알고리즘입니다.
배열의 값을 오름차순으로 정렬하면 다음과 같이 이진 검색의 의사 코드를 제공할 수 있습니다.

Agar tekshiriladigan element qolmagan bo‘lsa:
    Yo‘q deb qaytaramiz (return false)
Agar massivning[o‘rta elementi] 50 soniga teng bo‘lsa:
    Ha deb qaytaramiz (return true)
Agar massivning[o‘rta elementi] > 50:
    Massivning chap yarmidan qidiramiz
Agar massivning[o‘rta elementi] < 50:
    Massivning o‘ng yarmidan qidiramiz

---

빅오 표기법

Big O 표기법을 사용하여 알고리즘 실행에 걸리는 시간을 분석합니다. 다음 그래프를 살펴보겠습니다.

"입력 데이터 크기" – x축; "해결책의 시간" – y축;
알고리즘의 효율성은 곡선의 모양에 따라 결정됩니다.
O(n²)는 최악의 공연 시간입니다.
O(log n)은 가장 빠른 실행 시간입니다.

최악의 경우 n 단계가 필요할 수 있으므로 선형 검색 알고리즘의 실행 시간은 O(n)입니다.
그리고 이진 탐색 알고리즘이 작동하는데 걸리는 시간은 O(log n)인데, 최악의 경우 단계 수가 점점 줄어들기 때문입니다.

프로그래머가 관심을 갖는 두 가지 사례가 있습니다.

• 최악의 경우 또는 상한(상한).
• 최고의 경우 또는 하한(하한).

Ω 기호는 알고리즘의 최상의 경우 (하한)(예: Ω(n))을 나타내는 데 사용됩니다.

TH 기호는 상한과 하한이 동일한 경우, 즉 최고와 최악의 실행 시간이 동일한 경우를 나타냅니다.

---

정렬 알고리즘(정렬)

정렬은 정렬되지 않은 값 목록을 정렬된 값 목록으로 변경하는 과정입니다.
배열이 정렬되면 컴퓨터가 배열 안의 특정 요소를 검색하는 것이 훨씬 쉽습니다. 예를 들어 이진 검색 (이진 검색)은 정렬된 배열에서는 작동하지만 정렬되지 않은 배열에서는 작동하지 않습니다.

정렬 알고리즘에는 다양한 유형이 있습니다. 선택 정렬 (선택 정렬) 중 하나를 생각해 보겠습니다. 다음과 같은 배열이 주어집니다:

선택 방법 알고리즘의 의사 코드는 다음과 같습니다.

[20, 500, 10, 5, 100, 1, 50]

단계 분석:

• 처음으로 배열 요소를 살펴보는 데는 n - 1 단계가 소요됩니다.
• 두번째 n-2단계가 필요합니다.
• 이 논리를 계속하면 필요한 단계는 다음과 같이 표현될 수 있습니다.

Chapdan o‘ngga har bir eshikni tekshirish:
    Agar 50 soni bor bo‘lsa:
        Ha deb qaytaramiz (return true)
Yo‘q deb qaytaramiz (return false)

이 공식을 단순화하면 n(n-1)/2 또는 O(n²)이 됩니다.
따라서 선택 방법의 알고리즘은 최악의 경우 O(n²) 순서로 정렬합니다. 모든 값을 정렬해도 단계 수는 변하지 않으므로 O(n²) 순서가 가장 좋습니다.

---

버블 정렬 알고리즘(버블 정렬)

버블 정렬은 요소를 반복적으로 치환하여 더 큰 값을 "승격"시키는 또 다른 정렬 알고리즘입니다. 버블정렬 알고리즘의 의사코드는 다음과 같습니다.

배열을 정렬하면서 더 많은 부분이 정렬될 것임을 알기 때문에 아직 정렬되지 않은 쌍만 확인하면 됩니다.

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Butun sonlardan iborat massiv berilgan
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};

    // Kiritilgan sonni massivdan qidiramiz
    int n = get_int("Number: ");
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == n)
        {
            printf("Topildi\n");
            return 0;
        }
    }
    printf("Topilmadi\n");
    return 1;
}

따라서 버블 정렬 알고리즘은 배열이 정렬되지 않은 경우 최악의 경우 O(n²)에서 작동하고 배열이 이미 정렬된 경우 가장 좋은 경우 O(n)에서 작동합니다.

이 페이지에서 정렬 알고리즘이 어떻게 작동하는지 시각적으로 확인할 수 있습니다.

이 글은 CS50x 2024 소스를 사용했습니다.

위 내용은 CS- 3주차의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!