Menentukan kompleksitas untuk fungsi rekursif (notasi O Besar)

Saya memiliki Midterm Ilmu Komputer besok dan saya perlu bantuan menentukan kompleksitas fungsi rekursif ini. Saya tahu bagaimana menyelesaikan kasus-kasus sederhana, tetapi saya masih mencoba belajar bagaimana menyelesaikan kasus-kasus sulit ini. Ini hanya beberapa contoh masalah yang saya tidak tahu. Bantuan apa pun akan sangat dihargai dan akan sangat membantu dalam studi saya, Terima kasih!

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

Kompleksitas waktu, dalam notasi O Besar, untuk setiap fungsi, adalah dalam urutan numerik:

1. Fungsi pertama disebut berulang kali sebelum mencapai kasus dasar sehingga O(n)sering disebut linier .
2. Fungsi kedua disebut n-5 untuk setiap waktu, jadi kami mengurangi lima dari n sebelum memanggil fungsi, tetapi n-5 juga O(n). (Sebenarnya disebut urutan n / 5 kali. Dan, O (n / 5) = O (n)).
3. Fungsi ini adalah log (n) basis 5, untuk setiap kali kita membaginya dengan 5 sebelum memanggil fungsi demikian O(log(n))(basis 5), sering disebut logaritmik dan paling sering notasi O Besar dan analisis kompleksitas menggunakan basis 2.
4. Di keempat, itu O(2^n), atau eksponensial , karena masing-masing panggilan fungsi panggilan itu sendiri dua kali kecuali telah berulang n kali.

5. Sedangkan untuk fungsi terakhir, for loop membutuhkan n / 2 karena kita meningkat 2, dan rekursi mengambil n-5 dan karena for loop disebut secara rekursif karena itu kompleksitas waktu dalam (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2- 10n, karena perilaku asimptotik dan pertimbangan skenario terburuk atau batas atas yang diperjuangkan oleh O besar, kami hanya tertarik pada istilah terbesar sehingga O(n^2) .

   Semoga berhasil di ujian tengah semester Anda;)

Untuk kasus di mana n <= 0, T(n) = O(1). Oleh karena itu, kompleksitas waktu akan tergantung pada kapan n >= 0.

Kami akan mempertimbangkan kasus ini n >= 0di bagian di bawah ini.

1.

T(n) = a + T(n - 1)

di mana a adalah konstanta.

Dengan induksi:

T(n) = n * a + T(0) = n * a + b = O(n)

di mana a, b adalah beberapa konstanta.

2.

T(n) = a + T(n - 5)

di mana a adalah konstanta

Dengan induksi:

T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)

di mana a, b adalah beberapa konstanta dan k <= 0

3.

T(n) = a + T(n / 5)

di mana a adalah konstanta

Dengan induksi:

T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)

di mana a, b adalah beberapa konstanta

4.

T(n) = a + 2 * T(n - 1)

di mana a adalah konstanta

Dengan induksi:

T(n) = a + 2a + 4a + ... + 2^(n-1) * a + T(0) * 2^n 
     = a * 2^n - a + b * 2^n
     = (a + b) * 2^n - a
     = O(2 ^ n)

di mana a, b adalah beberapa konstanta.

5.

T(n) = n / 2 + T(n - 5)

di mana n adalah konstanta

Tulis ulang di n = 5q + rmana q dan r adalah bilangan bulat dan r = 0, 1, 2, 3, 4

T(5q + r) = (5q + r) / 2 + T(5 * (q - 1) + r)

Kami sudah q = (n - r) / 5, dan karena r <5, kami dapat menganggapnya konstan, jadiq = O(n)

Dengan induksi:

T(n) = T(5q + r)
     = (5q + r) / 2 + (5 * (q - 1) + r) / 2 + ... + r / 2 +  T(r)
     = 5 / 2 * (q + (q - 1) + ... + 1) +  1 / 2 * (q + 1) * r + T(r)
     = 5 / 4 * (q + 1) * q + 1 / 2 * (q + 1) * r + T(r)
     = 5 / 4 * q^2 + 5 / 4 * q + 1 / 2 * q * r + 1 / 2 * r + T(r)

Sejak r <4, kita dapat menemukan beberapa konstanta b sehingga b >= T(r)

T(n) = T(5q + r)
     = 5 / 2 * q^2 + (5 / 4 + 1 / 2 * r) * q + 1 / 2 * r + b
     = 5 / 2 * O(n ^ 2) + (5 / 4 + 1 / 2 * r) * O(n) + 1 / 2 * r + b
     = O(n ^ 2)

Salah satu cara terbaik yang saya temukan untuk memperkirakan kompleksitas algoritma rekursif adalah menggambar pohon rekursi. Setelah Anda memiliki pohon rekursif:

Complexity = length of tree from root node to leaf node * number of leaf nodes

1. Fungsi pertama akan memiliki panjang ndan jumlah simpul daun 1sehingga kompleksitasnyan*1 = n

2. Fungsi kedua akan memiliki panjang n/5dan jumlah node daun lagi 1sehingga kompleksitasnya n/5 * 1 = n/5. Itu harus diperkirakann

3. Untuk fungsi ketiga, karena ndibagi dengan 5 pada setiap panggilan rekursif, panjang pohon rekursif akan log(n)(base 5), dan jumlah node daun lagi 1 sehingga kompleksitas akan menjadilog(n)(base 5) * 1 = log(n)(base 5)

4. Untuk fungsi keempat karena setiap simpul akan memiliki dua simpul anak, jumlah simpul daun akan sama dengan (2^n)dan panjang pohon rekursif akan nsangat rumit (2^n) * n. Tetapi karena ntidak signifikan di depan (2^n), itu dapat diabaikan dan kompleksitas hanya dapat dikatakan demikian (2^n).

5. Untuk fungsi kelima, ada dua elemen yang memperkenalkan kompleksitas. Kompleksitas diperkenalkan oleh sifat fungsi rekursif dan kompleksitas yang diperkenalkan oleh forloop di setiap fungsi. Melakukan perhitungan di atas, kompleksitas yang diperkenalkan oleh sifat fungsi rekursif akan ~ ndan kompleksitas karena untuk loop n. Total kompleksitas akan menjadi n*n.

Catatan: Ini adalah cara penghitungan kompleksitas yang cepat dan kotor (tidak ada yang resmi!). Senang mendengar tanggapan tentang ini. Terima kasih.

Kita dapat membuktikannya secara matematis yang merupakan sesuatu yang saya lewatkan dalam jawaban di atas.

Ini secara dramatis dapat membantu Anda memahami cara menghitung metode apa pun. Saya sarankan membacanya dari atas ke bawah untuk memahami sepenuhnya bagaimana melakukannya:

1. T(n) = T(n-1) + 1Ini berarti bahwa waktu yang diperlukan untuk menyelesaikan metode sama dengan metode yang sama tetapi dengan n-1 yang T(n-1)sekarang kita tambahkan + 1karena itu waktu yang diperlukan untuk menyelesaikan operasi umum (kecuali T(n-1)). Sekarang, kita akan temukan T(n-1)sebagai berikut:T(n-1) = T(n-1-1) + 1 . Sepertinya kita sekarang dapat membentuk suatu fungsi yang dapat memberi kita semacam pengulangan sehingga kita dapat sepenuhnya memahami. Kami akan menempatkan sisi kanan T(n-1) = ...bukannya T(n-1)di dalam metode T(n) = ...yang akan memberi kita: T(n) = T(n-1-1) + 1 + 1yang T(n) = T(n-2) + 2atau dengan kata lain kita perlu menemukan kami hilang k: T(n) = T(n-k) + k. Langkah selanjutnya adalah mengambiln-k dan mengklaim bahwa n-k = 1karena pada akhir rekursi itu akan memakan waktu tepat O (1) kapann<=0. Dari persamaan sederhana ini kita sekarang tahu itu k = n - 1. Mari kita tempatkan kdi metode terakhir kita: T(n) = T(n-k) + kyang akan memberi kita: .T(n) = 1 + n - 1yang persis natauO(n)
2. Sama dengan 1. Anda dapat mengujinya sendiri dan melihat hasilnya O(n) .
3. T(n) = T(n/5) + 1seperti sebelumnya, waktu untuk menyelesaikan metode ini sama dengan waktu dengan metode yang sama tetapi dengan n/5alasan mengapa terikat T(n/5). Mari kita temukan T(n/5)seperti pada 1: T(n/5) = T(n/5/5) + 1yang mana T(n/5) = T(n/5^2) + 1. Tempat Mari T(n/5)dalam T(n)untuk perhitungan akhir: T(n) = T(n/5^k) + k. Sekali lagi seperti sebelumnya, n/5^k = 1yang n = 5^kpersis seperti menanyakan apa yang berkuasa 5, akan memberi kita n, jawabannya adalah log5n = k(log basis 5). Mari kita menempatkan temuan kami di T(n) = T(n/5^k) + ksebagai berikut: T(n) = 1 + lognyangO(logn)
4. T(n) = 2T(n-1) + 1apa yang kita miliki di sini pada dasarnya sama dengan sebelumnya tetapi kali ini kita menggunakan metode ini secara rekursif 2 kali sehingga kita gandakan dengan 2. Mari kita temukan T(n-1) = 2T(n-1-1) + 1yang mana T(n-1) = 2T(n-2) + 1. Tempat kita berikutnya seperti sebelumnya, mari kita tempatkan penemuan kita: T(n) = 2(2T(n-2)) + 1 + 1yang T(n) = 2^2T(n-2) + 2memberi kita T(n) = 2^kT(n-k) + k. Ayo temukank dengan mengklaim apa n-k = 1yang ada k = n - 1. Mari kita tempatkan ksebagai berikut: T(n) = 2^(n-1) + n - 1yang kira-kiraO(2^n)
5. T(n) = T(n-5) + n + 1Ini hampir sama dengan 4 tetapi sekarang kami menambahkan nkarena kami memiliki satu forloop. Ayo cari T(n-5) = T(n-5-5) + n + 1yang mana T(n-5) = T(n - 2*5) + n + 1. Mari kita tempatkan: T(n) = T(n-2*5) + n + n + 1 + 1)yang mana T(n) = T(n-2*5) + 2n + 2)dan untuk yang k: T(n) = T(n-k*5) + kn + k)lagi: n-5k = 1yang n = 5k + 1kira-kira n = k. Ini akan memberi kita: T(n) = T(0) + n^2 + nyang kira-kira O(n^2).

Saya sekarang merekomendasikan membaca sisa jawaban yang sekarang, akan memberi Anda perspektif yang lebih baik. Semoga berhasil memenangkan O besar :)

Kuncinya di sini adalah untuk memvisualisasikan pohon panggilan. Setelah selesai, kompleksitasnya adalah:

nodes of the call tree * complexity of other code in the function

istilah terakhir dapat dihitung dengan cara yang sama kita lakukan untuk fungsi iteratif normal.

Alih-alih, total node pohon lengkap dihitung sebagai

                  C^L - 1
                  -------  , when C>1
               /   C - 1
              /
 # of nodes =
              \    
               \ 
                  L        , when C=1

Di mana C adalah jumlah anak dari setiap simpul dan L adalah jumlah tingkatan pohon (termasuk root).

Sangat mudah untuk memvisualisasikan pohon itu. Mulai dari panggilan pertama (root node) kemudian gambar sejumlah anak yang sama dengan jumlah panggilan rekursif dalam fungsi. Juga bermanfaat untuk menulis parameter yang diteruskan ke panggilan sub-sebagai "nilai node".

Jadi, dalam contoh di atas:

1. pohon panggilan di sini adalah C = 1, L = n + 1. Kompleksitas dari sisa fungsi adalah O (1). Karenanya total kompleksitas adalah L * O (1) = (n + 1) * O (1) = O (n)

n     level 1
n-1   level 2
n-2   level 3
n-3   level 4
... ~ n levels -> L = n

2. pohon panggilan di sini adalah C = 1, L = n / 5. Kompleksitas dari sisa fungsi adalah O (1). Karenanya total kompleksitas adalah L * O (1) = (n / 5) * O (1) = O (n)

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5

3. pohon panggilan di sini adalah C = 1, L = log (n). Kompleksitas dari sisa fungsi adalah O (1). Karenanya total kompleksitas adalah L * O (1) = log5 (n) * O (1) = O (log (n))

n
n/5
n/5^2
n/5^3
... ~ log5(n) levels -> L = log5(n)

4. pohon panggilan di sini adalah C = 2, L = n. Kompleksitas dari sisa fungsi adalah O (1). Kali ini kami menggunakan rumus lengkap untuk jumlah node dalam pohon panggilan karena C> 1. Oleh karena itu kompleksitas totalnya adalah (C ^ L-1) / (C-1) * O (1) = (2 ^ n - 1 ) * O (1) = O (2 ^ n) .

               n                   level 1
      n-1             n-1          level 2
  n-2     n-2     n-2     n-2      ...
n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3    ...     
              ...                ~ n levels -> L = n

5. pohon panggilan di sini adalah C = 1, L = n / 5. Kompleksitas dari sisa fungsi adalah O (n). Karenanya total kompleksitas adalah L * O (1) = (n / 5) * O (n) = O (n ^ 2)

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5