Pertanyaan Big O, bagaimana Anda menghitung / mendekati itu?


Kebanyakan orang dengan gelar di CS pasti akan tahu apa Big O adalah singkatan. Ini membantu kita untuk mengukur bagaimana (dalam) efisien suatu algoritma sebenarnya dan jika Anda mengetahuinya kategori apa masalah yang ingin Anda selesaikan Anda dapat mengetahui apakah masih mungkin untuk memeras kinerja ekstra kecil itu.1

Tapi aku penasaran, bagaimana caranya kamu menghitung atau memperkirakan kompleksitas algoritme Anda?

1  tetapi seperti yang mereka katakan, jangan berlebihan, Optimasi prematur adalah akar dari semua kejahatan, dan pengoptimalan tanpa penyebab yang dibenarkan seharusnya juga pantas untuk nama itu.


784
2017-08-06 10:18


asal


Jawaban:


Saya seorang asisten profesor di universitas lokal saya di bidang Data Structures and Algorithms. Saya akan melakukan yang terbaik untuk menjelaskannya di sini dengan istilah sederhana, tetapi diperingatkan bahwa topik ini membutuhkan siswa saya beberapa bulan untuk akhirnya pegang. Anda dapat menemukan informasi lebih lanjut tentang Bab 2 dari Struktur Data dan Algoritma di Jawa Book.


Tidak ada prosedur mekanik yang bisa digunakan untuk mendapatkan BigOh.

Sebagai "buku masak", untuk mendapatkan BigOh dari sepotong kode Anda harus terlebih dahulu menyadari bahwa Anda membuat rumus matematika untuk menghitung berapa banyak langkah perhitungan dijalankan dengan masukan dari beberapa ukuran.

Tujuannya sederhana: untuk membandingkan algoritma dari sudut pandang teoritis, tanpa perlu mengeksekusi kode. Semakin sedikit jumlah langkah, semakin cepat algoritme.

Sebagai contoh, katakanlah Anda memiliki potongan kode ini:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

Fungsi ini mengembalikan jumlah semua elemen array, dan kami ingin membuat rumus untuk menghitung kompleksitas komputasional fungsi itu:

Number_Of_Steps = f(N)

Jadi kita punya f(N), fungsi untuk menghitung jumlah langkah komputasi. Input dari fungsi adalah ukuran dari struktur yang akan diproses. Ini berarti bahwa fungsi ini disebut seperti:

Number_Of_Steps = f(data.length)

Parameter N mengambil data.length nilai. Sekarang kita membutuhkan definisi fungsi yang sebenarnya f(). Ini dilakukan dari kode sumber, di mana setiap baris yang menarik diberi nomor dari 1 hingga 4.

Ada banyak cara untuk menghitung BigOh. Dari titik ini ke depan kita akan menganggap bahwa setiap kalimat yang tidak bergantung pada ukuran input data membutuhkan konstanta C jumlah langkah komputasi.

Kami akan menambahkan jumlah langkah-langkah individu dari fungsi, dan baik deklarasi variabel lokal maupun pernyataan pengembalian tergantung pada ukuran data larik.

Itu berarti bahwa jalur 1 dan 4 mengambil jumlah C masing-masing langkah, dan fungsinya agak seperti ini:

f(N) = C + ??? + C

Bagian selanjutnya adalah menentukan nilai dari for pernyataan. Ingat bahwa kita menghitung jumlah langkah komputasi, yang berarti bahwa tubuh for pernyataan dieksekusi N waktu. Itu sama dengan menambahkan C, Nwaktu:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

Tidak ada aturan mekanis untuk menghitung berapa kali tubuh for dijalankan, Anda harus menghitungnya dengan melihat apa yang dilakukan kode. Untuk menyederhanakan perhitungan, kami mengabaikan variabel inisialisasi, kondisi dan penambahan bagian dari for pernyataan.

Untuk mendapatkan BigOh yang sebenarnya kita membutuhkan Analisis asimtotik dari fungsi tersebut. Ini kira-kira dilakukan seperti ini:

  1. Singkirkan semua konstanta C.
  2. Dari f() ambil polinomium di dalamnya standard form.
  3. Bagilah persyaratan polinomium dan sortir mereka dengan laju pertumbuhan.
  4. Jaga yang tumbuh lebih besar saat N pendekatan infinity.

Kami f() memiliki dua istilah:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Mengambil semua itu C konstanta dan bagian redundan:

f(N) = 1 + N ^ 1

Karena istilah terakhir adalah yang tumbuh lebih besar saat f() mendekati infinity (pikirkan terus batas) ini adalah argumen BigOh, dan sum() fungsi memiliki BigOh:

O(N)

Ada beberapa trik untuk memecahkan beberapa trik: gunakan ringkasan kapanpun kamu bisa.

Sebagai contoh, kode ini dapat dengan mudah dipecahkan menggunakan ringkasan:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

Hal pertama yang perlu Anda tanyakan adalah urutan eksekusi foo(). Sementara yang biasa terjadi O(1), Anda perlu bertanya kepada profesor Anda tentang hal itu. O(1) berarti (hampir, sebagian besar) konstan C, terlepas dari ukurannya N.

Itu for Pernyataan pada kalimat nomor satu memang gampang-gampang susah. Sementara indeks berakhir 2 * N, kenaikannya dilakukan oleh dua. Itu berarti yang pertama for hanya dieksekusi N langkah-langkah, dan kita perlu membagi hitungan dengan dua.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

Nomor kalimat dua bahkan lebih sulit karena tergantung pada nilai i. Coba lihat: indeks saya mengambil nilai: 0, 2, 4, 6, 8, ..., 2 * N, dan yang kedua for dieksekusi: N kali yang pertama, N - 2 detik, N - 4 ketiga ... hingga tahap N / 2, yang kedua for tidak pernah dieksekusi.

Pada rumus, itu berarti:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

Sekali lagi, kami menghitung jumlah langkah. Dan menurut definisi, setiap penjumlahan harus selalu dimulai dari satu, dan berakhir pada angka yang lebih besar atau sama dari satu.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(Kami mengasumsikan itu foo() aku s O(1) dan mengambil C tangga.)

Kami punya masalah di sini: kapan i mengambil nilainya N / 2 + 1 ke atas, Summation batin berakhir pada angka negatif! Itu tidak mungkin dan salah. Kita perlu membagi penjumlahan menjadi dua, menjadi titik penting saat itu i dibutuhkan N / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

Sejak momen penting i > N / 2, batin for tidak akan dieksekusi, dan kita mengasumsikan kompleksitas eksekusi C konstan pada tubuhnya.

Sekarang ringkasan dapat disederhanakan menggunakan beberapa aturan identitas:

  1. Penjumlahan (w dari 1 hingga N) (C) = N * C
  2. Penjumlahan (w dari 1 hingga N) (A (+/-) B) = Penjumlahan (w dari 1 hingga N) (A) (+/-) Penjumlahan (w dari 1 hingga N) (B)
  3. Penjumlahan (w dari 1 hingga N) (w * C) = C * Penjumlahan (w dari 1 hingga N) (w) (C adalah konstanta, independen dari w)
  4. Penjumlahan (w dari 1 hingga N) (w) = (N * (N + 1)) / 2

Menerapkan beberapa aljabar:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

Dan BigOh adalah:

O(N²)

1390
2018-01-31 15:33



Big O memberikan batas atas kompleksitas waktu dari suatu algoritma. Ini biasanya digunakan bersama dengan memproses set data (daftar) tetapi dapat digunakan di tempat lain.

Beberapa contoh bagaimana itu digunakan dalam kode C.

Katakanlah kita memiliki susunan n elemen

int array[n];

Jika kita ingin mengakses elemen pertama dari array ini akan menjadi O (1) karena tidak peduli seberapa besar array, selalu membutuhkan waktu konstan yang sama untuk mendapatkan item pertama.

x = array[0];

Jika kami ingin menemukan nomor dalam daftar:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

Ini akan menjadi O (n) karena paling banyak kita harus melihat seluruh daftar untuk menemukan nomor kami. The Big-O masih O (n) meskipun kita mungkin menemukan nomor kami percobaan pertama dan jalankan melalui loop sekali karena Big-O menggambarkan batas atas untuk suatu algoritma (omega adalah untuk batas bawah dan theta adalah untuk terikat ketat) .

Ketika kita sampai ke loop bersarang:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

Ini adalah O (n ^ 2) karena untuk setiap laluan dari loop luar (O (n)) kita harus melalui seluruh daftar lagi sehingga n memperbanyak kita dengan n kuadrat.

Ini hampir tidak menggaruk permukaan tetapi ketika Anda bisa menganalisis lebih rumit algoritma matematika kompleks yang melibatkan bukti ikut bermain. Semoga ini bisa membiasakan Anda dengan dasar-dasar setidaknya.


190
2017-08-06 13:34



Meskipun mengetahui cara menentukan waktu O Big untuk masalah khusus Anda berguna, mengetahui beberapa kasus umum dapat sangat membantu Anda membuat keputusan dalam algoritme.

Berikut ini beberapa kasus yang paling umum, diangkat dari http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O (1) - Menentukan apakah suatu angka genap atau ganjil; menggunakan tabel lookup berukuran konstan atau tabel hash

O (logn) - Mencari item dalam array yang diurutkan dengan pencarian biner

O (n) - Mencari item dalam daftar yang tidak disortir; menambahkan dua angka n-digit

Di2) - Mengalikan dua angka n-digit dengan algoritma sederhana; menambahkan dua matriks n x n; semacam gelembung atau semacam penyisipan

Di3) - Mengalikan dua matriks n x n dengan algoritma sederhana

O (cn) - Menemukan solusi (tepat) untuk masalah salesman bepergian menggunakan pemrograman dinamis; menentukan apakah dua pernyataan logis ekuivalen menggunakan kekuatan brute

O (n!) - Memecahkan masalah salesman keliling melalui pencarian brute force

Din) - Sering digunakan sebagai ganti O (n!) Untuk mendapatkan formula yang lebih sederhana untuk kompleksitas asimtotik


87
2017-09-05 19:09



Pengingat kecil: big O notasi digunakan untuk menunjukkan asymptotic kompleksitas (yaitu, ketika ukuran masalah tumbuh hingga tak terbatas), dan menyembunyikan sebuah konstanta.

Ini berarti bahwa antara suatu algoritma dalam O (n) dan satu di O (n2), yang tercepat tidak selalu yang pertama (meskipun selalu ada nilai n sehingga untuk masalah ukuran> n, algoritma pertama adalah yang tercepat).

Perhatikan bahwa konstanta tersembunyi sangat tergantung pada penerapannya!

Juga, dalam beberapa kasus, runtime bukan merupakan fungsi deterministik dari ukuran n dari input. Ambil sortir menggunakan quick sort misalnya: waktu yang diperlukan untuk mengurutkan suatu array n elemen tidak konstan tetapi tergantung pada konfigurasi awal dari array.

Ada kerumitan waktu yang berbeda:

  • Kasus terburuk (biasanya yang paling sederhana untuk diketahui, meskipun tidak selalu sangat berarti)
  • Kasus rata-rata (biasanya lebih sulit untuk dicari ...)

  • ...

Pengantar yang bagus adalah Pengantar Analisis Algoritma oleh R. Sedgewick dan P. Flajolet.

Seperti yang Anda katakan, premature optimisation is the root of all evil, dan (jika mungkin) profiling benar-benar harus selalu digunakan ketika mengoptimalkan kode. Ia bahkan dapat membantu Anda menentukan kompleksitas algoritma Anda.


40
2017-08-23 20:43



Melihat jawabannya di sini saya pikir kita dapat menyimpulkan bahwa sebagian besar dari kita memang mendekati urutan algoritma oleh mencari dan menggunakan akal sehat daripada menghitungnya dengan, misalnya, metode utama seperti yang kami pikirkan di universitas. Dengan yang mengatakan saya harus menambahkan bahwa bahkan profesor mendorong kami (nanti) untuk benar-benar berpikir tentang itu bukan hanya menghitungnya.

Saya juga ingin menambahkan bagaimana hal itu dilakukan fungsi rekursif:

misalkan kita memiliki fungsi seperti (kode skema):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

yang secara rekursif menghitung faktorial dari bilangan yang diberikan.

Langkah pertama adalah mencoba dan menentukan karakteristik kinerja untuk tubuh fungsi saja dalam hal ini, tidak ada yang istimewa yang dilakukan di dalam tubuh, hanya perkalian (atau kembalinya nilai 1).

Sehingga kinerja untuk tubuh adalah: O (1) (konstan).

Selanjutnya coba dan tentukan ini untuk jumlah panggilan rekursif. Dalam hal ini kita memiliki panggilan rekursif n-1.

Sehingga kinerja untuk panggilan rekursif adalah: O (n-1) (order adalah n, karena kita membuang bagian-bagian yang tidak penting).

Kemudian satukan keduanya dan Anda kemudian memiliki kinerja untuk seluruh fungsi rekursif:

1 * (n-1) = O (n)


Peter, untuk menjawab masalah Anda yang diangkat; metode yang saya jelaskan di sini benar-benar menangani ini dengan cukup baik. Namun perlu diingat bahwa ini masih merupakan perkiraan dan bukan jawaban yang sepenuhnya benar secara matematis. Metode yang dijelaskan di sini juga merupakan salah satu metode yang diajarkan di universitas, dan jika saya ingat benar digunakan untuk algoritma yang jauh lebih maju daripada faktorial yang saya gunakan dalam contoh ini.
Tentu saja semuanya tergantung pada seberapa baik Anda dapat memperkirakan waktu berjalan dari tubuh fungsi dan jumlah panggilan rekursif, tetapi itu sama berlaku untuk metode lain.


26
2017-08-07 08:10



Jika biaya Anda adalah polinomial, simpan saja suku tertingginya, tanpa multiplier. Misalnya.:

O ((n / 2 + 1) * (n / 2)) = O (n2/ 4 + n / 2) = O (n2/ 4) = O (n2)

Ini tidak bekerja untuk seri yang tak terbatas, pikiran Anda. Tidak ada resep tunggal untuk kasus umum, meskipun untuk beberapa kasus umum, ketidaksetaraan berikut berlaku:

O (log N) <O (N) <O (N log N) <O (N2) <O (Nk) <O (en) <O (n!)


25
2018-01-31 13:30



Saya memikirkannya dalam hal informasi. Setiap masalah terdiri dari mempelajari sejumlah bit tertentu.

Alat dasar Anda adalah konsep titik-titik keputusan dan entropinya. Entropi titik keputusan adalah informasi rata-rata yang akan diberikan kepada Anda. Sebagai contoh, jika sebuah program berisi titik keputusan dengan dua cabang, itu entropi adalah jumlah dari probabilitas masing-masing cabang kali log2 dari kemungkinan inversi cabang itu. Itulah seberapa banyak Anda belajar dengan melaksanakan keputusan itu.

Misalnya, sebuah if pernyataan memiliki dua cabang, keduanya kemungkinan sama, memiliki entropi 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Jadi entropinya 1 bit.

Misalkan Anda mencari tabel item N, seperti N = 1024. Itu adalah masalah 10-bit karena log (1024) = 10 bit. Jadi jika Anda dapat mencari dengan pernyataan IF yang memiliki kemungkinan hasil yang sama, itu harus mengambil 10 keputusan.

Itulah yang Anda dapatkan dengan pencarian biner.

Misalkan Anda melakukan pencarian linear. Anda melihat elemen pertama dan menanyakan apakah itu yang Anda inginkan. Probabilitasnya adalah 1/1024, dan 1023/1024 bukan. Entropi dari keputusan itu adalah 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * sekitar 0 = sekitar 0,01 bit. Anda telah belajar sangat sedikit! Keputusan kedua tidak jauh lebih baik. Itulah sebabnya pencarian linear sangat lambat. Sebenarnya itu eksponensial dalam jumlah bit yang perlu Anda pelajari.

Misalkan Anda melakukan pengindeksan. Anggaplah tabel tersebut telah diurutkan sebelumnya menjadi banyak sampah, dan Anda menggunakan sebagian dari semua bit dalam kunci untuk mengindeks langsung ke entri tabel. Jika ada 1.024 sampah, entropinya adalah 1/1024 * log (1024) + 1/1024 * log (1024) + ... untuk semua 1.024 kemungkinan hasil. Ini adalah 1/1024 * 10 kali 1024 hasil, atau 10 bit entropi untuk operasi pengindeksan itu. Itulah mengapa pencarian pengindeksan cepat.

Sekarang pikirkan tentang penyortiran. Anda memiliki N item, dan Anda memiliki daftar. Untuk setiap item, Anda harus mencari di mana item tersebut masuk dalam daftar, dan kemudian menambahkannya ke daftar. Jadi menyortir membutuhkan kira-kira N kali jumlah langkah dari pencarian yang mendasari.

Jadi, berdasarkan keputusan biner yang memiliki hasil yang hampir sama kemungkinannya, semua mengambil langkah-langkah O (N log N). Algoritma sortir O (N) dimungkinkan jika didasarkan pada pencarian pengindeksan.

Saya telah menemukan bahwa hampir semua masalah kinerja algoritmik dapat dilihat dengan cara ini.


19
2018-03-10 13:24



Mari kita mulai dari awal.

Pertama-tama, menerima prinsip bahwa operasi sederhana tertentu pada data dapat dilakukan di O(1) waktu, yaitu, dalam waktu yang independen dari ukuran input. Operasi primitif ini di C terdiri dari

  1. Operasi aritmatika (misalnya + atau%).
  2. Operasi logis (mis., &&).
  3. Operasi perbandingan (mis., <=).
  4. Operasi pengaksesan struktur (misalnya pengindeksan array seperti A [i], atau pointer fol- lowing dengan -> operator).
  5. Tugas sederhana seperti menyalin nilai ke dalam variabel.
  6. Panggilan ke fungsi pustaka (misalnya, scanf, printf).

Pembenaran untuk prinsip ini memerlukan studi rinci tentang instruksi mesin (langkah primitif) dari komputer biasa. Setiap operasi yang dijelaskan dapat dilakukan dengan beberapa instruksi mesin kecil; seringkali hanya satu atau dua instruksi yang diperlukan. Sebagai akibatnya, beberapa jenis pernyataan dalam C dapat dieksekusi O(1) waktu, yaitu, dalam sejumlah waktu konstan tergantung pada input. Ini termasuk sederhana

  1. Pernyataan penugasan yang tidak melibatkan pemanggilan fungsi dalam ekspresi mereka.
  2. Baca pernyataan.
  3. Tulis pernyataan yang tidak memerlukan panggilan fungsi untuk mengevaluasi argumen.
  4. Pernyataan lompat putus, terus, goto, dan kembali berekspresi, di mana ekspresi tidak mengandung panggilan fungsi.

Dalam C, banyak for-loop dibentuk dengan menginisialisasi variabel indeks ke beberapa nilai dan incrementing variabel yang oleh 1 setiap kali sekitar loop. For-loop berakhir saat indeks mencapai batas. Misalnya, for-loop

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

menggunakan variabel indeks i. Ini menambah saya dengan 1 setiap kali sekitar loop, dan iterasi berhenti ketika saya mencapai n - 1.

Namun, untuk saat ini, fokus pada bentuk sederhana dari for-loop, di mana perbedaan antara nilai akhir dan nilai awal, dibagi dengan jumlah di mana variabel indeks bertambah memberitahu kita berapa kali kita berputar-putar. Jumlah itu tepat, kecuali ada cara untuk keluar dari loop melalui pernyataan lompat; itu adalah batas atas pada jumlah iterasi dalam hal apapun.

Sebagai contoh, for-loop iterates ((n − 1) − 0)/1 = n − 1 times, karena 0 adalah nilai awal dari i, n - 1 adalah nilai tertinggi yang dicapai oleh i (yaitu, ketika i mencapai n − 1, loop berhenti dan tidak ada iterasi terjadi dengan i = n − 1), dan 1 ditambahkan untuk i pada setiap iterasi loop.

Dalam kasus yang paling sederhana, di mana waktu yang dihabiskan dalam badan pengulangan adalah sama untuk masing-masing perulangan, kita dapat mengalikan batas atas oh yang besar untuk tubuh dengan jumlah kali di sekitar loop. Sebenarnya, kita harus melakukannya tambahkan O (1) waktu untuk menginisialisasi indeks loop dan O (1) waktu untuk perbandingan pertama indeks loop dengan membatasi, karena kami menguji sekali lagi daripada kami berkeliling. Namun, kecuali dimungkinkan untuk menjalankan loop nol kali, waktu untuk menginisialisasi loop dan tes batas sekali adalah istilah low-order yang dapat dijatuhkan oleh aturan penjumlahan.


Sekarang perhatikan contoh ini:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

Kami tahu itu baris (1) dibutuhkan O(1) waktu. Jelas, kita berputar-putar n kali, sebagai kita dapat menentukan dengan mengurangi batas bawah dari batas atas yang ditemukan di jalur (1) dan kemudian menambahkan 1. Karena tubuh, garis (2), membutuhkan waktu O (1), kita dapat mengabaikan waktu untuk menaikkan j dan waktu untuk membandingkan j dengan n, keduanya juga O (1). Dengan demikian, waktu berjalan dari garis (1) dan (2) adalah produk dari n dan O (1), yang mana O(n).

Demikian pula, kita dapat mengikat waktu berjalan dari lingkaran luar yang terdiri dari garis (2) sampai (4), yang mana

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

Kami telah menetapkan bahwa loop of lines (3) dan (4) membutuhkan waktu O (n). Dengan demikian, kita dapat mengabaikan waktu O (1) untuk menaikkan i dan untuk menguji apakah i <n in setiap iterasi, menyimpulkan bahwa setiap iterasi dari loop luar membutuhkan waktu O (n).

Inisialisasi i = 0 dari loop luar dan uji (n + 1) kondisi i <n juga mengambil O (1) waktu dan dapat diabaikan. Akhirnya, kami amati bahwa kami pergi sekitar loop luar n kali, mengambil O (n) waktu untuk setiap iterasi, memberikan total O(n^2) waktu berjalan.


Contoh yang lebih praktis.

enter image description here


17
2018-02-02 15:30



Jika Anda ingin menaksir urutan kode Anda secara empiris daripada dengan menganalisis kode, Anda dapat memasukkan serangkaian nilai yang semakin meningkat dari n dan waktu kode Anda. Plot timing Anda dalam skala log. Jika kode O (x ^ n), nilai-nilai harus jatuh pada garis kemiringan n.

Ini memiliki beberapa kelebihan dibanding hanya mempelajari kode. Untuk satu hal, Anda dapat melihat apakah Anda berada dalam rentang di mana waktu berjalan mendekati urutan asimtotiknya. Juga, Anda mungkin menemukan bahwa beberapa kode yang Anda pikir adalah perintah O (x) adalah benar-benar memesan O (x ^ 2), misalnya, karena waktu yang dihabiskan dalam panggilan perpustakaan.


11
2017-12-11 20:49



Pada dasarnya hal yang menghasilkan 90% waktu hanyalah menganalisis loop. Apakah Anda memiliki simpul bertingkat tunggal, ganda, tiga kali lipat? Anda memiliki O (n), O (n ^ 2), O (n ^ 3) waktu berjalan.

Sangat jarang (kecuali Anda menulis platform dengan pustaka basis yang luas (seperti misalnya, .NET BCL, atau C ++'s STL) Anda akan menemukan apa pun yang lebih sulit daripada hanya melihat loop Anda (untuk pernyataan, sementara, goto, dll ...)


9
2017-08-14 15:35