Kompleksitas waktu dari loop bersarang tiga

13

Harap pertimbangkan loop bertingkat tiga berikut:

for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            // statement

Pernyataan di sini dijalankan dengan tepat $n(n+1)(n+2)\over6$ kali. Bisakah seseorang tolong jelaskan bagaimana formula ini diperoleh? Terima kasih.

algorithms time-complexity algorithm-analysis Xin
sumber

1

Pertanyaan Rumus kompleksitas waktu dari loop bersarang mungkin juga menarik.

Juho

14

Anda dapat menghitung berapa kali loop terdalam dieksekusi dengan menghitung jumlah triplet $(i,j,k)$ yang dieksekusi.

Dengan kondisi loop kita tahu bahwa: . Kita bisa menguranginya menjadi masalah kombinatorik sederhana berikut. $1 \leq i \leq j \leq k \leq n$

Bayangkan kotak warna merah ditempatkan dalam array dari kiri ke kanan. $n+2$
Pilih 3 kotak dari kotak dan beri warna biru. $n+2$
Bentuk triplet sebagai berikut:
- = 1 + jumlah kotak berwarna merah di sebelah kiri kotak biru pertama. $i$
- = 1 + jumlah kotak berwarna merah di sebelah kiri kotak biru kedua. $j$
- = 1 + jumlah kotak berwarna merah di sebelah kiri kotak biru ketiga. $k$

Jadi, kita hanya perlu menghitung jumlah cara memilih 3 kotak dari kotak yaitu $n+2$ . $n+2 \choose 3$

rizwanhudda
sumber

2

Jawaban bagus! Nilai tepat i, j, k tidak penting. Kita hanya perlu tahu bahwa setiap kotak biru dapat ditempatkan di posisi yang mungkin dan bahwa posisi mereka dibatasi: yang ke-2 selalu datang setelah tanggal 1 dan sebelum ke-3.

Dávid Natingga

@rizwanhudda Hapus kecuali untuk bagian

di

. Bisakah Anda jelaskan?

terlihat seperti angka yang benar.

+ 2

$+2$

n + 2

$n+2$

n + 3

$n+3$

saadtaame

1

@saadtaame Ya. Anda dapat membayangkan memiliki

kotak merah, tetapi memiliki kebebasan untuk memilih 3 kotak merah untuk melukis biru dari antara "

kotak merah", karena Anda tidak dapat mewarnai kotak pertama sebagai biru (Karena

)

n + 3

$n+3$

n + 2

$n+2$

i \geq 1

$i \geq 1$

rizwanhudda

3

bagi saya, lebih mudah untuk melihat loop dalam dieksekusi kali dan jumlah total eksekusi dalam loop dalam adalah $n-i$

$(n-i)+(n-i-1)+(n-i-2)+\ldots+1$

ini dapat ditulis ulang sebagai dan dieksekusi kali, sehingga jumlah total eksekusi adalah $\sum_{j=0}^{n-i} n-i-j$ $n$

\sum_{i = 0}^{n} \sum_{j = 0}^{n - i} n - i - j = \frac{n (n + 1) (n + 2)}{6}

$\sum_{i=0}^{n}\sum_{j=0}^{n-i} n-i-j=\frac{n(n+1)(n+2)}{6}$

andy mcevoy
sumber

Tantangan bagi Anda: Bayangkan Anda memiliki loop bersarang-x. Menurut jawaban sebelumnya yang akan dieksekusi (n + x-1) pilih x kali. Bagaimana Anda menghitung formula Anda?

Dávid Natingga

untungnya OP tidak meminta x-nested! Bagaimana jawaban lain yang diberikan meluas ke loop bersarang x? Jawaban saya seharusnya mendapatkan lebih banyak jumlah dari 0 hingga n, 0 hingga n-i_1, 0 hingga n-i_2, ..., 0 hingga n-i_x. Tetapi saya tidak tahu bagaimana cara menghitungnya.

andy mcevoy

1

Jawabannya tidak berkembang secara eksplisit untuk x umum, tetapi proses penalaran yang disajikan mudah diikuti untuk loop bersarang x. Anda hanya menambahkan lebih banyak kotak biru. Saya juga tidak tahu bagaimana saya akan menghitung jumlah yang lebih banyak.

Dávid Natingga

Kompleksitas waktu dari loop bersarang tiga

Jawaban: