Apa karakteristik dari algoritma kompleksitas waktu ?

Terkadang mudah untuk mengidentifikasi kompleksitas waktu dari sebuah algoritma yang saya teliti dengan cermat. Algoritma dengan dua loop bersarang jelas . Algoritma yang mengeksplorasi semua kemungkinan kombinasi dari N kelompok dari dua nilai yang jelas 2 ^ N .N 2 N 2 $N$$N^2$$N$$2^N$

Namun saya tidak tahu bagaimana "menemukan" suatu algoritma dengan kompleksitas $\Theta(N \log N)$ . Implementasi mergesort rekursif, misalnya, adalah satu. Apa karakteristik umum dari mergesort atau algoritma $\Theta(N \log N)$ yang akan memberi saya petunjuk jika saya menganalisisnya?

Saya yakin ada lebih dari satu cara algoritma dapat dari kompleksitas $\Theta(N \log N)$ , jadi setiap dan semua jawaban dihargai. BTW Saya mencari karakteristik dan tip umum, bukan bukti yang kuat.

Pola dasar Anda adalah algoritma divide-and-menaklukkan , yang membagi (dan menggabungkan kembali) pekerjaan dalam waktu linier dan berulang pada potongan-potongan. Menggabungkan semacam bekerja seperti itu: menghabiskan waktu membagi input menjadi dua bagian yang kira-kira sama, mengurutkan masing-masing bagian secara rekursif, dan menghabiskan waktu menggabungkan dua bagian yang diurutkan.O ( n ) Θ ( n $\Theta(n \log n)$$O(n)$$\Theta(n)$

Secara intuitif, melanjutkan ide membagi-dan-taklukkan, setiap tahap pembagian memakan waktu linier secara total, karena peningkatan jumlah keping untuk membagi sama persis dengan penurunan ukuran keping, karena waktu yang diambil oleh pembagian adalah linier. Total waktu berjalan adalah produk dari total biaya tahap divisi dikalikan dengan jumlah tahap divisi. Karena ukuran potongan dibelah dua pada setiap waktu, ada , sehingga total waktu berjalan adalah . (Hingga konstanta multiplikasi, dasar logaritma tidak relevan.)n ⋅ log ( n $\log_2(n)$$n \cdot \log(n)$

Menempatkannya dalam persamaan (), salah satu cara untuk memperkirakan waktu berjalan dari algoritma semacam itu adalah dengan menyatakannya secara rekursif: . Jelas bahwa algoritme ini membutuhkan lebih dari waktu linier, dan kita dapat melihat lebih banyak dengan membagi dengan : Ketika menggandakan, meningkat dengan jumlah yang konstan: meningkat secara logaritma, atau dengan kata lain, .T ( n ) = 2 T ( n / 2 ) + Θ ( n ) n T ( n $T(n)$$T(n) = 2 T(n/2) + \Theta(n)$$n$nT(n)/nT(n)/nT(n)=Θ(nlogn

Ini adalah contoh dari pola yang lebih umum: teorema master . Untuk algoritma rekursif yang membagi input dari ukuran menjadi lembar ukuran dan memakan waktu untuk melakukan pembagian dan rekombinasi, waktu berjalan memuaskan . Ini mengarah ke bentuk tertutup yang tergantung pada nilai-nilai dan dan bentuk . Jika dan , teorema master menyatakan bahwa .$n$$a$$n/b$$f(n)$$T(n) = a \cdot T(n/b) + f(n)$$a$$b$$f$$a = b$$f(n) = \Theta(n)$$T(n) = \Theta(n \log n)$

Dua kategori algoritma lainnya yang memerlukan waktu :$\Theta(n \log n)$

Algoritma tempat setiap item diproses secara bergantian, dan dibutuhkan waktu logaritmik untuk memproses setiap item (mis. HeapSort atau banyak algoritma geometri komputasi bidang sapuan bidang).

Algoritma di mana waktu berjalan didominasi oleh langkah pemilahan pra-pemrosesan. (Misalnya, dalam algoritma Kruskal untuk pohon spanning minimum, kami dapat mengurutkan tepi berdasarkan berat sebagai langkah pertama).

Kategori lain: Algoritma di mana output memiliki ukuran , dan karenanya Θ ( n log n ) waktu berjalan adalah linier dalam ukuran output .$\Theta(n \log n)$$\Theta(n \log n)$

Meskipun detail dari algoritma tersebut sering menggunakan teknik divide-and-menaklukkan, mereka tidak harus begitu. Run-time secara fundamental berasal dari pertanyaan yang diajukan, dan jadi saya pikir perlu disebutkan secara terpisah.

Ini muncul dalam struktur data yang didasarkan pada pohon pencarian biner augmented, di mana setiap node menyimpan struktur data ukuran linier untuk mencari daun di subtree node itu. Struktur data seperti itu sering muncul dalam pencarian rentang geometris, dan seringkali didasarkan pada skema dekomposisi . Lihat Survei Agarwal .

Untuk contoh konkret, pertimbangkan pohon rentang , dibangun untuk menjawab pertanyaan rentang orthogonal dua dimensi. Meskipun ruang itu kemudian dikurangi menggunakan beberapa teknik kompresi untuk mengemas beberapa objek menjadi satu kata, versi buku teks (dan paling intuitif) dari struktur data membutuhkan ruang (setiap daun disimpan dalam struktur tambahan di setiap simpul di jalur dari daun ke root, atau di O ( log n ) tempat), dan algoritma konstruksi membutuhkan waktu linier dalam kebutuhan ruang .$O(n \log n)$$O(\log n)$

Kompleksitas muncul dari algoritme divide and conquer yang membagi input mereka ke dalam k k dengan ukuran yang kira-kira sama dalam waktu O ( n ) , beroperasi pada bagian-bagian ini secara rekursif, dan kemudian menggabungkannya dalam waktu O ( n ) . Jika Anda hanya beroperasi pada beberapa bagian, waktu berjalan turun menjadi O ( n ) .$O(n\log n)$$k$$O(n)$$O(n)$$O(n)$

Itu biasanya adalah algoritme dari varietas "divide and conquer", di mana biaya untuk membagi dan menggabungkan sub-solusi tidak "terlalu besar". Lihatlah FAQ ini untuk melihat jenis perulangan apa yang memunculkan perilaku ini.

Biasanya, algoritma Divide-and-menaklukkan akan menghasilkan kompleksitas O (N log N).

Contoh umum dari loop ( bukan algoritma per se) yang berjalan di adalah sebagai berikut:$O(n \log n)$

for (i = 0; i < constant; i++){
    for(j = 0; j < n; j++){
        // Do some O(1) stuff on the input
    }
}

// Alternative Variant:
for (i = 0; i < constant; i++){
    for(j = n; j < constant; j++){
        // Do some O(1) stuff on the input
    }
}

(perhatikan bahwa loop bersarang ini bukan . Juga perhatikan bahwa loop tidak diarsipkan dan tidak pula rekursif.)$O(n^2)$

Saya tidak bisa memberikan contoh konkret dari algoritma yang menggunakan loop ini, tetapi sering muncul ketika coding algoritma kustom.