CS - 第 3 週

アルゴリズム は、問題を解決するために特定の順序で与えられる一連の命令です。アルゴリズムは速度と占有メモリ量が異なります。プログラミング プロセスでは、ほとんどのアルゴリズムはデータ検索 (searching) と並べ替え (sorting) に基づいています。データ取得アルゴリズムについて学びましょう:

リニアサーチ（リニアサーチ）

次の配列を与えてみましょう:

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

配列を視覚化すると、次のように 7 つの赤いキャビネットが並べて表示されます。

この配列から 50 個の数値を見つける必要があります。コンピューターは各ロッカーをチェックして 50 番を見つける必要があります。このプロセスを、配列内の特定の数値、文字、またはその他の要素を検索することを "search" と呼びます。
配列をアルゴリズムに渡し、食器棚を開けてそこに 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) です。これは、最悪の場合、ステップ数がどんどん減少するためです。

プログラマにとって興味深いケースが 2 つあります:

• 最悪の場合または上限 (上限).
• 最良の場合または下限 (下限).

記号

Ω は、アルゴリズムの最良のケース (下限)、たとえば Ω(n) を示すために使用されます。

記号

TH は、上限と下限が同じ場合、つまり、最良の実行時間と最悪の実行時間が同じ場合を示します。

---

ソートアルゴリズム (ソート)

並べ替えは、順序なしの値のリストを順序付きの値に変更するプロセスです。
配列がソートされると、コンピューターは配列内の特定の要素を検索するのがはるかに簡単になります。たとえば、二分検索 (二分検索) は、ソートされた配列では機能しますが、ソートされていない配列では機能しません。

並べ替えアルゴリズムにはさまざまな種類があります。そのうちの 1 つである 選択ソート (選択ソート) を考えてみましょう。次のような配列を与えてみましょう:

選択方法アルゴリズムの擬似コードは次のとおりです:

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

ステップ分析:

• 初めて配列要素を確認するには、n - 1 ステップかかります。
• 2 回目は 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 中国語 Web サイトの他の関連記事を参照してください。