Jenis lain dari analisis waktu berjalan selain kasus terburuk, rata-rata, dll?

Berikut adalah beberapa cara untuk menganalisis waktu berjalan suatu algoritma:

1) Analisis kasus terburuk: Menjalankan waktu pada contoh terburuk.

2) Analisis kasus rata-rata: Waktu berjalan yang diharapkan pada contoh acak.

3) Analisis diamortisasi: Rata-rata waktu berjalan pada urutan kejadian terburuk.

4) Analisis yang diperhalus: Waktu berjalan yang diharapkan pada contoh gangguan yang terburuk secara acak.

5) Analisis kasus umum: Menjalankan waktu pada yang terburuk dari semua kecuali sebagian kecil contoh.

Pertanyaan saya: Apakah ini daftar lengkap?

Instance optimality adalah properti algoritma yang sangat menarik. Seseorang dapat menggeneralisasi gagasan tentang optimalitas contoh dan menghasilkan gagasan menarik yang mengejutkan yang mencakup analisis kasus terburuk dan rata-rata.

Meskipun tidak sepenuhnya berada di bawah bidang analisis algoritma tradisional, itu menarik dalam dirinya sendiri. Gagasan dalam sebuah makalah oleh Afshani-Barbay-Chan (FOCS '09) yang membahas algoritma geometris menganggap kinerja algoritma tidak menyadari urutan-input (yang relevan dengan masalah khusus mereka).

Ini mungkin terlihat untuk menggeneralisasi sebagai berikut: Untuk setiap partisi algoritma input ke dalam kelas kesetaraan dan menganggap kinerja algoritma sebagai semacam statistik kolektif atas kinerja rata-rata untuk masing-masing kelas ekivalensi ini.

Analisis kasus terburuk hanya melihat input sebagai kelas ekivalensi individual dan menghitung waktu berjalan maksimum. Analisis kasus rata-rata melihat kelas ekivalensi sepele yang merupakan satu tunggal yang terdiri dari semua input. Dalam makalah Afshani-Barbay-Chan, algoritma mereka optimal jika input dipartisi ke dalam kelas permutasi (yaitu, urutan kinerja yang tidak diketahui).

Tidak jelas apakah ini mengarah pada paradigma baru dari analisis algoritma. Tentu saja Tim Roughgarden memiliki beberapa contoh motivasi yang sangat baik dan mencakup berbagai metode untuk menganalisis algoritma.

Saya punya dua lagi untuk daftar, yang agak mirip.

1. $O(c^n n^{O(1)})$$1 < c < 2$$k$$O(2^k n^{O(1)})$$k$$n$

2. $O(n \log n + k)$$k$

$O(n \log n)$

Sepertinya Analisis Parameterisasi untuk algoritma polinomial-waktu, dan tampaknya analisis peka keluaran termasuk dalam kategori ini.

Ada juga analisis " probabilitas tinggi " (untuk algoritma acak), di mana untuk setiap kasus tertentu Anda khawatir tentang seberapa baik algoritma Anda akan melakukan sebagian besar waktu, tetapi benar-benar dapat memberikan sebagian kecil dari waktu. Ini biasa dalam teori belajar.

Anda dapat menambahkan keacakan ke algoritme Anda, dan menggabungkannya dengan semua hal di atas. Kemudian Anda akan mendapatkan, misalnya, waktu berjalan yang diperkirakan sebagai kasus terburuk (contoh kasus terburuk, tetapi dirata-rata atas semua urutan kemungkinan dari koin acak membalik dalam algoritma) dan waktu berjalan terburuk dengan probabilitas tinggi (sekali lagi, kasus terburuk, tetapi probabilitas atas koin acak membalik dalam algoritme).

Analisis bijective adalah cara untuk membandingkan dua algoritma (Spyros Angelopoulos, Pascal Schweitzer: Paging dan daftar pembaruan di bawah analisis bijective. J. ACM 60, 2013): Secara kasar, Algoritma A lebih baik daripada Algoritma B pada input dengan panjang n jika ada bijih f dari input panjang n sehingga A berkinerja pada input x setidaknya sebaik B pada f (x).

Analisis kompetitif

Digunakan untuk membandingkan algoritma online dengan algoritma offline kinerja. Lihat halaman wikipedia . Masalah Pembaruan Daftar adalah contoh klasik.

Analisis kompetitif Dalam algoritme penggantian halaman , satu metode mengalahkan yang lainnya dengan mengurangi sedikit halaman. Lebih sedikit halaman yang hilang menggambarkan "kurang waktu berjalan". Selain itu, analisis kompetitif adalah metode untuk membandingkan dua metode secara relatif. Buku referensi yang bagus adalah "KOMPUTASI DAN ANALISIS KOMPETITIF ONLINE" dari Allan Borodin.