CS- Minggu 3

Algoritma ialah satu set arahan yang diberikan dalam urutan tertentu untuk menyelesaikan masalah. Algoritma berbeza dalam kelajuan dan berapa banyak memori yang mereka duduki. Dalam proses pengaturcaraan, kebanyakan algoritma adalah berdasarkan carian data (mencari) dan menyusun (mengisih). Mari kita berkenalan dengan algoritma pengambilan data:

Carian linear (carian linear)

Biarlah kita diberikan tatasusunan berikut:

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

Apabila menggambarkan tatasusunan, ia boleh dilihat sebagai tujuh kabinet merah bersebelahan seperti ini:

Kita perlu mencari 50 nombor daripada tatasusunan ini. Komputer mesti menyemak setiap loker untuk mencari nombor 50. Kami memanggil proses ini, iaitu, mencari nombor tertentu, aksara atau elemen lain dalam tatasusunan "carian".
Kami boleh menghantar tatasusunan kami kepada algoritma dan meminta algoritma untuk membuka almari dan menentukan sama ada nombor 50 ada di sana. Akibatnya, algoritma akan menjawab kami “ya” atau “tidak” (benar atau salah).

Kami boleh membina algoritma menggunakan arahan berikut:

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

Arahan di atas boleh dibaca oleh manusia pseudokod dan merupakan representasi yang lebih mudah bagi arahan yang diberikan kepada komputer.

Kami boleh melaksanakan algoritma carian linear dalam C menggunakan kod berikut:

#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;
}

Di sini carian linear dilakukan menggunakan gelung for.
return 0 bermakna program telah selesai dengan jayanya dan program telah keluar.
return 1 - menunjukkan bahawa ralat berlaku dalam atur cara.

---

Carian binari

Carian Binari ialah algoritma lain yang digunakan untuk mencari nombor 50.
Jika nilai dalam tatasusunan diisih dalam tertib menaik, kita boleh memberikan pseudokod carian binari seperti berikut:

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

---

Notasi O besar

Notasi Big O notasi digunakan untuk menganalisis masa yang diperlukan untuk menjalankan algoritma. Mari lihat graf berikut:

"Saiz data input" – paksi-x; "Masa untuk penyelesaian" – paksi-y;
Kecekapan algoritma ditentukan oleh bentuk lengkungnya:
O(n²) ialah masa persembahan yang paling teruk.
O(log n) ialah masa pelaksanaan terpantas.

Masa berjalan bagi algoritma carian linear ialah O(n), kerana dalam kes paling teruk n langkah mungkin diperlukan.
Dan masa yang diperlukan untuk algoritma carian binari berfungsi ialah O(log n), kerana dalam kes yang paling teruk, bilangan langkah semakin berkurangan.

Terdapat dua kes yang menarik minat pengaturcara:

• Kes terburuk atau sempadan atas (batas atas).
• Huruf terbaik atau sempadan bawah (batas bawah).

Simbol

Ω digunakan untuk menandakan kes terbaik (batas bawah) algoritma, contohnya Ω(n).

Simbol

TH menunjukkan kes di mana sempadan atas dan bawah adalah sama, iaitu, masa larian terbaik dan paling teruk adalah sama.

---

Algoritma pengisihan (Isih)

Isih ialah proses menukar senarai nilai yang tidak tersusun kepada yang tersusun.
Apabila tatasusunan diisih, lebih mudah bagi komputer untuk mencari elemen tertentu di dalamnya. Contohnya, carian binari (carian binari) berfungsi pada tatasusunan yang diisih tetapi bukan pada tatasusunan yang tidak diisih.

Terdapat banyak jenis algoritma pengisihan. Mari kita pertimbangkan salah satu daripadanya isihan pilihan (isih pilihan). Marilah kita diberikan tatasusunan seperti ini:

Pseudokod algoritma kaedah pemilihan adalah seperti berikut:

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

Analisis langkah:

• Berjalan melalui elemen tatasusunan untuk kali pertama mengambil n - 1 langkah.
• Kali kedua n - 2 langkah diperlukan.
• Melanjutkan logik ini, langkah-langkah yang diperlukan boleh dinyatakan sebagai:

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

Mempermudahkan formula ini, kita mendapat: n(n-1)/2 atau O(n²).
Jadi, algoritma kaedah pemilihan disusun mengikut susunan O(n²) dalam kes yang paling teruk. Walaupun semua nilai diisih, bilangan langkah tidak berubah, jadi kes terbaik adalah dalam susunan O(n²).

---

Algoritma isihan gelembung (Isih gelembung)

Isih gelembung ialah satu lagi algoritma pengisihan yang mana kami "mempromosikan" nilai yang lebih besar dengan mengubah suai elemen berulang kali.

Pseudokod algoritma isihan gelembung adalah seperti berikut:

#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;
}

Semasa kami mengisih tatasusunan, kami tahu bahawa lebih banyak daripadanya akan diisih, jadi kami hanya perlu menyemak pasangan yang belum diisih.
Oleh itu, algoritma isihan gelembung berfungsi dalam kes terburuk O(n²) jika tatasusunan tidak diisih dan dalam kes terbaik O(n) jika tatasusunan sudah diisih.

Kita dapat melihat secara visual cara algoritma pengisihan berfungsi dalam halaman ini.

Artikel ini menggunakan sumber CS50x 2024.

Atas ialah kandungan terperinci CS- Minggu 3. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!