Cara menganalisis algoritma menggunakan kerumitan masa dan kerumitan ruang dalam C++

Cara menganalisis algoritma menggunakan kerumitan masa dan kerumitan ruang dalam C++

Kerumitan masa dan kerumitan ruang ialah ukuran berapa lama algoritma dijalankan dan ruang yang diperlukannya. Dalam pembangunan perisian, kita sering perlu menilai kecekapan algoritma untuk memilih penyelesaian yang optimum. Sebagai bahasa pengaturcaraan berprestasi tinggi, C++ menyediakan struktur data yang kaya dan perpustakaan algoritma, serta keupayaan pengkomputeran yang berkuasa dan mekanisme pengurusan memori.

Artikel ini akan memperkenalkan cara menggunakan algoritma analisis kerumitan masa dan kerumitan ruang dalam C++, dan menerangkan cara menganalisis dan mengoptimumkan melalui contoh kod tertentu.

1. Analisis kerumitan masa

Kerumitan masa ialah ukuran menganggarkan masa pelaksanaan sesuatu algoritma. Ia biasanya dinyatakan dalam tatatanda O besar (O(n)), yang mewakili hubungan antara masa berjalan algoritma dan pertumbuhan saiz input n. Kerumitan masa biasa termasuk O(1), O(log n), O(n), O(n log n), dan O(n^2).

Berikut mengambil dua algoritma pengisihan biasa (isih gelembung dan isihan cepat) sebagai contoh untuk memperkenalkan cara menganalisis kerumitan masanya.

1. Isih buih

Isih buih ialah algoritma pengisihan yang mudah tetapi kurang cekap. Idea asasnya ialah bermula dari elemen pertama, bandingkan saiz elemen bersebelahan satu demi satu, dan tukar dalam tertib menaik atau menurun sehingga keseluruhan urutan disusun.

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {       
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换arr[j]和arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Dalam isihan gelembung, bilangan pelaksanaan gelung luar ialah n-1, manakala bilangan pelaksanaan gelung dalam ialah (n-1) + (n-2) + ... + 1 = n( n- 1)/2. Oleh itu, kerumitan masa jenis gelembung ialah O(n^2).

2. Isih cepat

Isih cepat ialah algoritma isihan yang cekap. Ia menggunakan idea bahagi dan takluk, memilih elemen penanda aras dalam jujukan, membahagikan jujukan kepada dua jujukan, di mana unsur-unsur dalam satu jujukan lebih kecil daripada unsur tanda aras, dan unsur dalam jujukan yang lain lebih besar. daripada atau sama dengan elemen penanda aras, dan kemudian Kedua-dua urutan dengan cepat diisih secara berasingan.

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
  
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            // 交换arr[i]和arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 交换arr[i+1]和arr[high]
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
  
    return (i + 1);
}
  
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Dalam isihan pantas, satu elemen penanda aras dipilih dan dibahagikan setiap kali Kerumitan masa operasi partition ialah O(n). Dalam kes yang paling teruk, iaitu, setiap partition membahagikan jujukan kepada dua urutan panjang 1 dan n-1, kerumitan masa isihan pantas ialah O(n^2). Tetapi dalam kes purata, kerumitan masa isihan pantas ialah O(n log n).

Analisis kerumitan masa bagi kedua-dua algoritma pengisihan ini memberitahu kita bahawa apabila ia melibatkan data berskala besar, pengisihan pantas adalah lebih cekap daripada pengisihan gelembung.

2. Analisis kerumitan ruang

Kerumitan ruang ialah ukuran ruang memori yang diperlukan oleh algoritma. Ia termasuk kod program, pembolehubah global, pembolehubah tempatan, memori yang diperuntukkan secara dinamik, dsb.

Berikut mengambil pengiraan jujukan Fibonacci sebagai contoh untuk memperkenalkan cara menganalisis kerumitan ruang algoritma.

int fibonacci(int n) {
    int* fib = new int[n+1];
    fib[0] = 0;
    fib[1] = 1;
  
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
  
    return fib[n];
}

Dalam kod di atas, kami menggunakan tatasusunan yang diperuntukkan secara dinamik untuk menyimpan hasil pengiraan, jadi ruang tambahan yang diperlukan adalah berkaitan dengan saiz input n. Oleh itu, kerumitan ruang bagi jujukan Fibonacci ialah O(n). Perlu diingatkan bahawa memori yang diperuntukkan secara dinamik perlu dikeluarkan secara manual selepas digunakan untuk mengelakkan kebocoran memori.

Dalam pembangunan sebenar, kami perlu memilih struktur data dan algoritma yang sesuai berdasarkan senario perniagaan tertentu dan keperluan masalah untuk mengoptimumkan kerumitan masa dan kerumitan ruang serta menyelesaikan kesesakan prestasi.

Kesimpulan

Artikel ini memperkenalkan cara menggunakan algoritma analisis kerumitan masa dan kerumitan ruang dalam C++ dan menerangkannya dengan contoh kod konkrit. Dalam pembangunan sebenar, kita harus menggunakan sepenuhnya struktur data dan perpustakaan algoritma dalam C++, dan menggabungkan analisis kerumitan masa dan kerumitan ruang untuk memilih penyelesaian yang optimum. Ini akan membantu meningkatkan prestasi dan kecekapan program, memberikan pengguna pengalaman yang lebih baik.

Atas ialah kandungan terperinci Cara menganalisis algoritma menggunakan kerumitan masa dan kerumitan ruang dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!