Contoh: Menentukan O besar

Bahagian ini memberikan beberapa contoh penentuan O Besar untuk pernyataan pengulangan, urutan dan pemilihan.

Contoh 1

Pertimbangkan kerumitan masa untuk gelung berikut:

untuk (int i = 1; i <= n; i++) {
k = k + 5;
}

Ia adalah masa yang tetap, c, untuk melaksanakan

k = k + 5;

Memandangkan gelung dilaksanakan n kali, kerumitan masa untuk gelung ialah

T(n) = (pemalar c)*n = O(n).

Analisis teori meramalkan prestasi algoritma. Untuk melihat prestasi algoritma ini, kami menjalankan kod dalam atur cara di bawah untuk mendapatkan masa pelaksanaan untuk n = 1000000, 10000000, 100000000 dan 100000000.

Analisis kami meramalkan kerumitan masa linear untuk gelung ini. Seperti yang ditunjukkan dalam output sampel, apabila saiz input meningkat 10 kali, masa jalan meningkat kira-kira 10 kali. Perlaksanaan mengesahkan ramalan.

Contoh 2

Apakah kerumitan masa untuk gelung berikut?

untuk (int i = 1; i <= n; i++) {
untuk (int j = 1; j <= n; j++) {
k = k + i + j;
}
}

Ia adalah masa yang tetap, c, untuk melaksanakan

k = k + i + j;

Gelung luar dilaksanakan n kali. Untuk setiap lelaran dalam gelung luar, gelung dalam dilaksanakan n kali. Oleh itu, kerumitan masa untuk gelung ialah

T(n) = (pemalar c)*n*n = O(n^2)

Algoritma dengan kerumitan masa O(n^2) dipanggil algoritma kuadratik dan ia mempamerkan kadar pertumbuhan kuadratik. Algoritma kuadratik berkembang dengan cepat apabila saiz masalah bertambah. Jika anda menggandakan saiz input, masa untuk algoritma adalah empat kali ganda. Algoritma dengan gelung bersarang selalunya kuadratik.

Contoh 3

Pertimbangkan gelung berikut:

untuk (int i = 1; i <= n; i++) {
untuk (int j = 1; j <= i; j++) {
k = k + i + j;
}
}

Gelung luar dilaksanakan n kali. Untuk i = 1, 2, c , gelung dalam dilaksanakan satu kali, dua kali dan n kali. Oleh itu, kerumitan masa untuk gelung ialah

Contoh 4

Pertimbangkan gelung berikut:

untuk (int i = 1; i <= n; i++) {
untuk (int j = 1; j <= 20; j++) {
k = k + i + j;
}
}

Gelung dalam dilaksanakan 20 kali, dan gelung luar n kali. Oleh itu, kerumitan masa untuk gelung ialah

T(n) = 20*c*n = O(n)

Contoh 5

Pertimbangkan urutan berikut:

untuk (int j = 1; j <= 10; j++) {
k = k + 4;
}

untuk (int i = 1; i <= n; i++) {
untuk (int j = 1; j <= 20; j++) {
k = k + i + j;
}
}

Gelung pertama dilaksanakan 10 kali, dan gelung kedua 20 * n kali. Oleh itu, kerumitan masa untuk gelung ialah

T(n) = 10*c + 20*c*n = O(n)

Contoh 6

Pertimbangkan pernyataan pilihan berikut:

jika (senarai.mengandungi(e)) {
System.out.println(e);
}
lain
untuk (Objek t: senarai) {
System.out.println(t);
}

Andaikan senarai mengandungi n elemen. Masa pelaksanaan untuk list.contains(e) ialah O(n). Gelung dalam klausa else mengambil masa O(n). Oleh itu, kerumitan masa untuk keseluruhan pernyataan ialah

Contoh 7

Pertimbangkan pengiraan a^n untuk integer n. Algoritma mudah akan mendarab n kali, seperti berikut:

hasil = 1;
untuk (int i = 1; i <= n; i++)
hasil *= a;

Algoritma mengambil masa O(n). Tanpa kehilangan keluasan, andaikan n = 2^k. Anda boleh menambah baik algoritma menggunakan skema berikut:

hasil = a;
untuk (int i = 1; i <= k; i++)
hasil = hasil * keputusan;

Algoritma mengambil masa O(logn). Untuk n sewenang-wenangnya, anda boleh menyemak algoritma dan membuktikan bahawa kerumitan masih O(logn).

Untuk kesederhanaan, kerana 0(logn) = 0(log2n) = 0(logan), asas malar diabaikan.

Atas ialah kandungan terperinci Contoh: Menentukan O besar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!