Akankah perangkat keras / implementasi mempengaruhi kompleksitas waktu / ruang dari algoritma?

Saya bahkan bukan mahasiswa CS, jadi ini mungkin pertanyaan bodoh, tapi tolong bawa saya ...

Di era pra-komputer, kita hanya bisa menerapkan struktur data array dengan sesuatu seperti array laci. Karena salah satu harus mencari laci dengan sesuai indeks sebelum penggalian nilai dari itu, kompleksitas waktu array lookup , dengan asumsi pencarian biner.$O(log(n))$

Namun, penemuan komputer membuat perbedaan besar. Komputer modern dapat membaca dari RAM mereka begitu cepat sehingga kami sekarang menganggap kompleksitas waktu pencarian array menjadi (bahkan secara teknis tidak demikian, karena dibutuhkan lebih banyak waktu untuk memindahkan register pada jarak yang lebih jauh, dll)$O(1)$

Contoh lain adalah kamus Python. Sementara orang mungkin mendapatkan kompleksitas akses kamus dengan metode magis kelebihan penulisan yang buruk (atau nasib buruk yang sangat buruk, yaitu kunci yang memiliki banyak tabrakan hash), biasanya dianggap O ( 1 ) . Dalam hal ini, kompleksitas waktu tergantung pada implementasi tabel hash dari kamus Python, dan implementasi kunci dari fungsi hash.$O(n)$__hash__$O(1)$

Apakah ini menyiratkan bahwa perangkat keras / implementasi dapat mempengaruhi kompleksitas waktu dari algoritma? (Walaupun kedua contoh adalah tentang struktur data, bukan algoritma, yang terakhir dibangun di atas yang sebelumnya, dan saya belum pernah mendengar tentang kompleksitas waktu struktur data, jadi saya menggunakan istilah "algoritma" di sini)

Bagi saya, algoritma itu abstrak dan konseptual, yang sifat-sifatnya seperti kompleksitas ruang / waktu tidak boleh terpengaruh oleh apakah mereka diterapkan dengan cara tertentu, tetapi apakah itu?

Yakin. Pasti. Inilah cara mendamaikan ketidaknyamanan Anda.

Ketika kami menganalisis waktu berjalan algoritma, kami melakukannya sehubungan dengan model komputasi tertentu . Model perhitungan menentukan hal-hal seperti waktu yang diperlukan untuk melakukan setiap operasi dasar (apakah pencarian array waktu atau O ( 1 ) waktu?). Waktu berjalan dari algoritma mungkin tergantung pada model perhitungan.$O(\log n)$$O(1)$

Setelah Anda memilih model perhitungan, analisis algoritme adalah latihan matematika yang murni abstrak, konseptual, yang tidak lagi tergantung pada perangkat keras.

Namun, dalam praktiknya kami biasanya ingin memilih model perhitungan yang mencerminkan realitas perangkat keras kami - setidaknya hingga tingkat yang wajar. Jadi, jika perangkat keras berubah, kami mungkin memutuskan untuk menganalisis algoritme kami di bawah model komputasi yang berbeda yang lebih sesuai dengan perangkat keras baru. Itulah bagaimana perangkat keras dapat memengaruhi waktu berjalan.

Alasan ini tidak jelas adalah karena, di kelas pengantar, kita sering tidak berbicara tentang model perhitungan. Kami hanya secara implisit membuat beberapa asumsi, tanpa pernah membuatnya eksplisit. Itu masuk akal, untuk tujuan pedagogis, tetapi memiliki biaya - menyembunyikan aspek analisis ini. Sekarang kamu tau.

Saya pikir ada kesalahpahaman mendasar dalam pertanyaan itu. Anda membandingkan orang yang menemukan objek dalam daftar yang diurutkan (misalnya, halaman tertentu dalam sebuah buku, diberikan nomornya) dengan komputer yang mencari item dari array.

Alasan mengapa mantan membutuhkan waktu $O(\log n)$ dan yang terakhir membutuhkan waktu $O(1)$adalah tidak bahwa komputer begitu cepat sehingga dapat melakukan pencarian biner dalam sekejap mata. Sebaliknya, itu karena komputer tidak menggunakan pencarian biner sama sekali. Komputer memiliki mekanisme untuk langsung mengambil item dari array tanpa mencari. Untuk mengambil isi sel array, komputer hanya memberi tahu pengontrol memori analog "Beri saya halaman tujuh belas", pengontrol memori mengatur voltase pada kabel alamat ke representasi biner tujuh belas dan data kembali.

Jadi, ya, perangkat keras (yaitu, model perhitungan) memang memengaruhi waktu berjalan algoritme, seperti yang dijelaskan DW , tetapi bukan itu yang menjadi dasar contoh akses array Anda.

Tidak, perangkat keras tidak memengaruhi kompleksitas algoritma.

Tapi , itu mempengaruhi pilihan algoritma, dan itu dapat mempengaruhi kegunaan analisis kompleksitas ke titik di mana analisis menjadi cukup banyak tidak berarti (atau hanya karena kepentingan akademis).

Menemukan laci yang tepat (sebagai mengakses elemen array) menggunakan algoritma "buka Nth elemen langsung dengan indeks", bukan algoritma "pencarian linear" atau "lakukan pencarian biner". Algoritme tidak diubah, tetapi pilihannya.

Di sisi lain, analisis kompleksitas itu sendiri, atau lebih tepatnya kebermaknaannya, sangat dipengaruhi oleh perangkat keras.

Banyak algoritma yang terkenal dengan analisis kompleksitasnya adalah berkinerja buruk atau bahkan tidak berguna dalam praktik karena faktor konstan yang tidak signifikan sama sekali tidak signifikan, tetapi mendominasi .

Atau, karena asumsi yang dulunya benar (atau sebagian besar benar) tidak berlaku lagi. Misalnya, misalnya, setiap operasi sebagian besar sama (hanya perbedaan kecil yang konstan yang tidak masalah), atau tidak membuat perbedaan lokasi memori mana yang Anda akses dalam urutan yang mana. Dengan analisis kompleksitas, Anda dapat menyimpulkan bahwa beberapa algoritma jauh lebih unggul karena hanya membutuhkan operasi yang sangat banyak. Dalam praktiknya, Anda mungkin menemukan bahwa setiap operasi menyebabkan kehilangan cache yang dijamin (atau lebih buruk lagi, kesalahan halaman), yang memperkenalkan k yang sangat besar sehingga tidak lagi tidak signifikan, tetapi mendominasi segalanya.
Jika algoritma A membutuhkan 500 operasi untuk memproses dataset dengan ukuran tertentu dan algoritma B hanya membutuhkan 5, tetapi B menyebabkan 5 kesalahan yang masing-masing membakar dua puluh juta siklus, maka terlepas dari apa yang mungkin dikatakan oleh para analis atau akal sehat, A lebih baik.

Hal ini menyebabkan kejutan lucu seperti misalnya di Cuckoo Hashing beberapa tahun yang lalu. Yang jauh lebih unggul karena [daftar panjang manfaat]. Setelah hype mendingin, ternyata itu jauh lebih rendah karena dijamin dua kesalahan cache (kesalahan, untuk set data yang lebih besar) pada setiap akses.

Hal serupa terjadi pada pengidentifikasian dan pemrosesan himpunan bagian data. Seringkali, solusi yang tepat saat ini adalah: "lakukan saja semuanya" , yaitu alih-alih mencari tahu apa yang Anda butuhkan untuk melakukan dan melakukan itu, proses dataset lengkap secara linear bahkan jika Anda mungkin hanya membutuhkan setengahnya. Karena, percaya atau tidak, itu lebih cepat karena tidak ada dugaan cabang, tidak ada cache salah, tidak ada kesalahan halaman.
Perlu membaca 8kB pertama dan 3kB terakhir dari file 3MB? Nah, baca file lengkap, dan buang apa yang tidak Anda inginkan, karena mencari di antaranya akan sepuluh kali lebih lambat daripada hanya membaca hal yang lengkap.

Gunakan peta karena memiliki kompleksitas logaritmik? Atau tabel hash, yang memiliki waktu akses konstan? Konstan terdengar luar biasa. Nah, untuk apa pun dengan kurang dari seribu hal (tergantung pada perangkat keras, ukuran data, dan pola akses), pencarian linier mungkin sama baiknya atau lebih baik. Mengherankan.

Jadi, bukan algoritma yang terpengaruh, tetapi kegunaannya, dan pilihannya.