Pertanyaan Menjalankan waktu penghitungan semacam


Saya mencoba memahami waktu berjalan dari penghitungan semacam. Dalam catatan saya, dikatakan, dengan asumsi ukuran array A adalah n, dan k adalah jumlah kali setiap angka terjadi,

 Counting-Sort(A,k) {
   for (i=1; i <= k; i++) // initialize number counters to 0
       times[i] = 0;

   for (j=1; j <= length[A]; j++) // decide how many times each
       times[A[j]]++;                  // number appears in the input

  // form the sorted array
  m=1;
    for ( i=1; i <= k; i++)    // consider each number in the range
         for ( j=1; j <= times[ i ]; j++) { // generate that number in 
            A[m]=i;                   // the output as many times as
            m++;                      // it occurs in the input
         }
  }

Biarkan tsaya menunjukkan jumlah kali iterasi loop dalam untuk masing-masing i. Ketika kita melihat pada loop bersarang di bagian bawah kode, perhatikan bahwa, setiap kali loop dalam iterasi, kita menempatkan nomor baru ke tempat yang benar dalam array output.   Oleh karena itu: jumlah tsaya (dari i = 1 ke k) = n.

Saya tidak mengerti mengapa jumlah ini sama dengan n. Lingkaran luar iterates kali k, dan loop batin dapat iterate paling banyak n kali, jadi harus O (nk). Bisakah seseorang menjelaskan? Terima kasih


4
2018-03-21 12:02


asal


Jawaban:


Seperti yang Anda lihat untuk pengulangan

m=1;
for ( i=1; i <= k; i++)    // consider each number in the range
     for ( j=1; j <= times[ i ]; j++) { // generate that number in 
        A[m]=i;                   // the output as many times as
        m++;                      // it occurs in the input
     }

kompleksitasnya akan sama dengan berapa kali tubuh siklus dalam dieksekusi. Kapan i = 1, itu dieksekusi times[1] kali, kapan i = 2 => times[2] kali, dan sebagainya, kapan i = k, times[k] waktu. Jadi total tubuh bagian dalam dieksekusi times[1] + times[2] + ... + times[k] kali, dan jumlah itu sama dengan n, karena setiap elemen dihitung satu kali.


0
2018-03-21 15:51



Algoritma

Counting Sort, dikenal juga sebagai Histogram Sort

n = length of input Array

k = number of unique symbols that appear in the input Array
  • Inisialisasi dibutuhkan k waktu

  • Menghitung mengambil n waktu

  • Enumerasi mengambil Sum { Count(i) } = n waktu

Kompleksitas

Time = k + n + n = 2n+k

Time ~ O(2n+k) = O(n+k)

Space = n + k ~ O(n+k)

2
2018-03-22 07:15



Nada-nadanya tidak sepenuhnya benar. k adalah angka tertinggi yang muncul di larik Anda (yaitu memiliki angka dari 1 hingga k). Jadi, mari melangkah melalui algoritme:

  1. Inisialisasi k "sampah": O(k)
  2. Hitung seberapa sering setiap angka terjadi: O(n)
    • Jumlah nilai di semua tempat sampah adalah persis n, karena itulah jumlah entri yang kami miliki secara total dalam larik
  3. Iterate over the bins: O(k)
    • Setel sama banyak elemen dalam larik hasil sebagai nampan mewakili: tampaknya O(n)

Yang penting di sini adalah kita tahu bahwa meskipun kita mengulanginya k sampah dan bisa, secara umum, hingga n nilai-nilai yang diwakili oleh masing-masing bin, kita mengatur sampah sehingga, di semua iterasi dari loop luar, loop dalam masih berjalan untuk total n waktu. Oleh karena itu, kompleksitas total dari langkah ini sebenarnya O(n).

Jika kita mengabaikan pengetahuan tambahan tentang isi tempat sampah, Anda akan benar.

Sekarang ada perubahan terakhir: jika k > n, sebenarnya ada di O(k) daripada O(n)! Karena sekarang lingkaran luar adalah hal yang "berjalan lebih sering".

Saya harap ini masuk akal.


0
2018-03-21 13:21