Kompleksitas operasi dasar pencarian dan pengurutan algoritma [ditutup]

Wiki memiliki lembar contekan yang bagus, tetapi tidak melibatkan no. dari perbandingan atau swap. (meskipun tidak. swap biasanya menentukan kompleksitasnya). Jadi saya membuat yang berikut ini. Apakah info berikut ini benar? Harap beri tahu saya jika ada kesalahan, saya akan memperbaikinya.

Jenis Penyisipan:

• Kasus Rata-Rata / Kasus Terburuk: ; terjadi ketika input sudah diurutkan dalam urutan menurun$\Theta(n^2)$
• Kasus Terbaik: ; ketika input sudah diurutkan$\Theta(n)$
• Jumlah perbandingan: dalam kasus terburuk & dalam kasus terbaik$\Theta(n^2)$$\Theta(n)$
• Jumlah swap: dalam kasus terburuk / rata-rata & dalam kasus Terbaik$\Theta(n^2)$$0$

Sortir Pilihan:

• Kasus Rata-Rata / Kasus Terburuk / Kasus Terbaik:$\Theta(n^2)$
• Jumlah perbandingan:$\Theta(n^2)$
• Jumlah swap: dalam kasus terburuk / rata-rata & dalam kondisi terbaik Paling banyak algoritmanya membutuhkan N swap, setelah Anda menukar elemen ke tempatnya, Anda tidak pernah menyentuhnya lagi.$\Theta(n)$$0$

Gabungkan Sortir:

• Kasus Rata-Rata / Kasus Terburuk / Kasus terbaik: ; tidak masalah sama sekali apakah input diurutkan atau tidak$\Theta(nlgn)$
• Jumlah perbandingan: dalam kasus terburuk & dalam kasus terbaik; dengan asumsi kita menggabungkan dua array ukuran n & m di mana$\Theta(n+m)$$\Theta(n)$$n<m$
• Jumlah swap: Tidak ada swap! [tetapi membutuhkan memori ekstra, bukan jenis di tempat]

Sortir Cepat:

• Kasus Terburuk: ; input yang terjadi sudah diurutkan$\Theta(n^2)$
• Kasus Terbaik: ; ketika pivot membagi array tepat setengah$\Theta(nlogn)$
• Jumlah perbandingan: dalam kasus terburuk & dalam kasus terbaik$\Theta(n^2)$$\Theta(nlogn)$
• Jumlah swap: dalam kasus terburuk & dalam kasus terbaik$\Theta(n^2)$$0$

Semacam gelembung:

• Kasus Terburuk:$\Theta(n^2)$
• Kasus Terbaik: ; pada sudah diurutkan$\Theta(n)$
• Jumlah perbandingan: dalam kasus terburuk & terbaik$\Theta(n^2)$
• Jumlah swap: dalam kasus terburuk & dalam kasus terbaik$\Theta(n^2)$$0$

Pencarian Linier:

• Kasus Terburuk: ; kunci pencarian tidak ada atau elemen terakhir$\Theta(n)$
• Kasus Terbaik: ; elemen pertama$\Theta(1)$
• Jumlah perbandingan: dalam kasus terburuk & dalam kasus terbaik$\Theta(n)$$1$

Pencarian Biner:

• Kasus terburuk / Kasus rata-rata:$\Theta(logn)$
• Kasus Terbaik: ; ketika kunci adalah elemen tengah$\Theta(1)$
• Jumlah perbandingan: dalam kasus terburuk / rata-rata & dalam kasus terbaik$\Theta(logn)$$1$

1. Saya hanya mempertimbangkan algoritme pencarian & penyortiran dasar.
2. Diasumsikan di atas bahwa algoritma pengurutan menghasilkan output dalam urutan menaik
3. Sumber: CLRS yang mengagumkan dan Wiki ini

Untuk algoritma umum perbandingan kasus terburuk semacam gelembung adalah Tetapi untuk algoritme kasus khusus di mana Anda menambahkan tanda untuk menunjukkan bahwa telah terjadi pertukaran pada pass sebelumnya. Jika tidak ada swap maka kita keluar dari loop karena array sudah diurutkan. Dalam hal ini perbandingannya adalah bukan 0.$\Theta(n^2)$$n$

Untuk Quick sort Anda telah menyebutkan bahwa swap kasus terburuk adalah . Skenario kasus terburuk untuk penyortiran cepat adalah ketika semua elemen dalam urutan diurutkan sehingga tidak akan ada swap sehingga harus nol.$n^2$