Waktu proses big-theta dari dua loop bersarang linier, loop bagian dalam berjalan setengah kali lipat untuk setiap iterasi loop luar.

Saya mengalami banyak masalah dengan masalah algoritma ini. Saya seharusnya menemukan analisis theta besar dari algoritma berikut:

function example(n):
    int j=n
    for i=0;i<n;i++:
        doSomethingA()
        for k=0;k<=j;k++:
            doSomethingB()
        j/=2

Pendekatan saya adalah membagi keseluruhan eksekusi algoritma menjadi dua bagian. Satu bagian di mana doSomethingA() dan doSomethingB() keduanya dipanggil, dan bagian kedua setelah j menjadi 0 dan hanya doSomethingA() yang dipanggil hingga program berhenti.

Dengan pendekatan ini, Anda memiliki bagian 1 yang terjadi untuk iterasi Logn pada loop luar, bagian 2 terjadi untuk iterasi n-logn pada loop luar.

Berapa kali loop dalam berjalan dibelah dua untuk setiap proses, sehingga total berapa kali loop tersebut berjalan harus 2n-1. Jadi runtime untuk bagian 1 harus (2n-1)*c, sebuah konstanta. Saya tidak sepenuhnya yakin apakah ini valid

Untuk bagian 2, usaha di dalam perulangan selalu konstan, dan perulangan berulang (n-logn) kali.

Jadi kita punya ((2n-1)+(n-logn))*c

Saya tidak yakin apakah pekerjaan yang saya lakukan sampai di sini sudah benar, saya juga tidak yakin bagaimana melanjutkannya. Intuisi saya memberi tahu saya bahwa ini adalah O(n), tetapi saya tidak yakin bagaimana merasionalisasikannya dalam big-theta. Selain itu, mungkin seluruh pendekatan saya memiliki kelemahan. Bagaimana saya harus menyerang pertanyaan seperti ini? Jika pendekatan saya valid, bagaimana saya harus menyelesaikannya?

Terima kasih.


algorithm computer-science big-o asymptotic-complexity
person Conor James Thomas Warford Hen    schedule 15.02.2018    source sumber
comment
Itu Big O no thetas :) Juga Big O hanyalah notasi (banyak digunakan dalam matematika): yang Anda analisis adalah kompleksitas waktu.   -  person giorgiga    schedule 15.02.2018
comment
Saya bingung. Big-O dan Big-Theta adalah konsep yang berbeda bukan? Saya diminta menemukan Big-Theta, bukan Big-O.   -  person Conor James Thomas Warford Hen    schedule 15.02.2018
comment
Ya, O dan Theta adalah konsep yang berbeda. Theta sama dengan (O dan Omega). Secara kasar O adalah semacam batas atas, Omega semacam batas bawah dan oleh karena itu Theta adalah perilaku asimtotik yang sama persis.   -  person Henry    schedule 15.02.2018
comment
Keburukan saya: Saya benar-benar lupa bahwa itu benar-benar ada - saya kira terlalu banyak tahun lagi dari dunia akademis :-)   -  person giorgiga    schedule 15.02.2018
comment
Perulangan dalam setidaknya akan berjalan satu kali pada setiap iterasi perulangan luar (bahkan ketika j telah mencapai 0, perulangan akan berjalan satu kali)   -  person Henry    schedule 15.02.2018

Jawaban (1)


arrow_upward
1
arrow_downward

Lebih mudah untuk menyelidiki seberapa sering doSomethingA dan doSomethingB dieksekusi.

Untuk doSomethingA jelas n kali.

Untuk doSomethingB kita mendapatkan (n+1) + (n/2+1) + (n/4+1) + ... + 1 jadi kira-kira 2n + n. 2n dari n+n/2+n/4+... dan n dari penjumlahan 1s.

Secara keseluruhan kita mendapatkan O(n) dan juga Theta(n) karena Anda memerlukan setidaknya Omega(n) seperti yang terlihat dari n kali doSomethingA dieksekusi.

person Henry    schedule 15.02.2018