Apakah ada kasus di mana Anda lebih suka algoritma kompleksitas waktu-O lebih tinggi daripada yang lebih rendah?

Apakah ada kasus di mana Anda lebih suka O(log n)kompleksitas O(1)waktu daripada kompleksitas waktu? Atau O(n)untuk O(log n)?

Apakah Anda punya contoh?

Mungkin ada banyak alasan untuk memilih algoritma dengan kompleksitas waktu O lebih tinggi daripada yang lebih rendah:

• sebagian besar waktu, kompleksitas big-O yang lebih rendah lebih sulit untuk dicapai dan membutuhkan implementasi yang terampil, banyak pengetahuan dan banyak pengujian.
• big-O menyembunyikan detail tentang konstanta : algoritma yang berkinerja 10^5lebih baik dari sudut pandang O-besar daripada 1/10^5 * log(n)( O(1)vs O(log(n)), tetapi untuk yang paling masuk akal n, yang pertama akan berkinerja lebih baik. Sebagai contoh kompleksitas terbaik untuk perkalian matriks adalah O(n^2.373)tetapi konstanta sangat tinggi sehingga tidak ada (setahu saya) perpustakaan komputasi menggunakannya.
• big-O masuk akal ketika Anda menghitung sesuatu yang besar. Jika Anda perlu mengurutkan array dari tiga angka, itu sangat penting apakah Anda menggunakan O(n*log(n))atau O(n^2)algoritma.
• kadang-kadang keuntungan dari kompleksitas waktu kecil dapat benar-benar diabaikan. Sebagai contoh ada tango pohon struktur data yang memberikan O(log log N)kompleksitas waktu untuk menemukan item, tetapi ada juga pohon biner yang menemukan di sama O(log n). Bahkan untuk sejumlah besar n = 10^20perbedaannya dapat diabaikan.
• kompleksitas waktu bukanlah segalanya. Bayangkan sebuah algoritma yang berjalan di O(n^2)dan membutuhkan O(n^2)memori. Mungkin lebih disukai dari O(n^3)waktu ke waktu dan O(1)ruang ketika n tidak terlalu besar. Masalahnya adalah Anda bisa menunggu untuk waktu yang lama, tetapi sangat ragu Anda dapat menemukan RAM yang cukup besar untuk menggunakannya dengan algoritma Anda
• paralelisasi adalah fitur yang baik di dunia terdistribusi kami. Ada algoritma yang mudah diparalelkan, dan ada beberapa yang tidak bisa diparalelkan sama sekali. Terkadang masuk akal untuk menjalankan algoritma pada 1000 mesin komoditas dengan kompleksitas lebih tinggi daripada menggunakan satu mesin dengan kompleksitas yang sedikit lebih baik.
• di beberapa tempat (keamanan) kompleksitas dapat menjadi persyaratan. Tidak ada yang ingin memiliki algoritma hash yang dapat hash sangat cepat (karena orang lain dapat memaksa Anda lebih cepat)
• Meskipun ini tidak terkait dengan pergantian kompleksitas, tetapi beberapa fungsi keamanan harus ditulis dengan cara untuk mencegah serangan waktu . Mereka sebagian besar tetap di kelas kompleksitas yang sama, tetapi dimodifikasi sedemikian rupa sehingga selalu dibutuhkan kasus yang lebih buruk untuk melakukan sesuatu. Salah satu contoh adalah membandingkan bahwa string sama. Dalam sebagian besar aplikasi masuk akal untuk berbuka puasa jika byte pertama berbeda, tetapi dalam keamanan Anda masih akan menunggu sampai akhir untuk menyampaikan kabar buruk.
• seseorang mematenkan algoritma kompleksitas yang lebih rendah dan lebih ekonomis bagi perusahaan untuk menggunakan kompleksitas yang lebih tinggi daripada membayar uang.
• beberapa algoritma beradaptasi dengan baik untuk situasi tertentu. Jenis penyisipan, misalnya, memiliki kompleksitas waktu rata-rata O(n^2), lebih buruk daripada quicksort atau mergesort, tetapi sebagai algoritma online, ia dapat mengurutkan daftar nilai secara efisien saat diterima (sebagai input pengguna) di mana sebagian besar algoritma lain hanya dapat beroperasi secara efisien pada daftar nilai lengkap.

Selalu ada konstanta tersembunyi, yang bisa lebih rendah pada algoritma O (log n ). Sehingga bisa bekerja lebih cepat dalam praktiknya untuk data kehidupan nyata.

Ada juga masalah ruang (misalnya berjalan di atas pemanggang roti).

Ada juga kekhawatiran waktu pengembang - O (log n ) mungkin 1000 × lebih mudah untuk diterapkan dan diverifikasi.

Saya terkejut tidak ada yang menyebutkan aplikasi yang terikat memori.

Mungkin ada algoritma yang memiliki operasi floating point lebih sedikit baik karena kompleksitasnya (yaitu O (1) < O (log n )) atau karena konstanta di depan kompleksitas lebih kecil (yaitu 2 n ² <6 n ² ) . Apapun, Anda mungkin masih lebih memilih algoritma dengan FLOP lebih banyak jika algoritma FLOP yang lebih rendah lebih terikat memori.

Yang saya maksud dengan "terikat memori" adalah bahwa Anda sering mengakses data yang selalu keluar dari cache. Untuk mengambil data ini, Anda harus menarik memori dari ruang memori Anda yang sebenarnya ke dalam cache sebelum dapat melakukan operasi. Langkah pengambilan ini seringkali sangat lambat - jauh lebih lambat dari operasi Anda sendiri.

Oleh karena itu, jika algoritme Anda memerlukan lebih banyak operasi (namun operasi ini dilakukan pada data yang sudah ada dalam cache [dan karena itu tidak diperlukan pengambilan]), itu masih akan melakukan algoritma Anda dengan lebih sedikit operasi (yang harus dilakukan di luar -cache data [dan karena itu membutuhkan pengambilan]) dalam hal waktu dinding yang sebenarnya.

Dalam konteks di mana keamanan data menjadi perhatian, algoritma yang lebih kompleks mungkin lebih disukai daripada algoritma yang lebih kompleks jika algoritma yang lebih kompleks memiliki ketahanan yang lebih baik terhadap serangan waktu .

Alistra berhasil tetapi gagal memberikan contoh jadi saya akan melakukannya.

Anda memiliki daftar 10.000 kode UPC untuk apa yang dijual toko Anda. UPC 10 digit, bilangan bulat untuk harga (harga dalam uang) dan 30 karakter deskripsi untuk tanda terima.

Pendekatan O (log N): Anda memiliki daftar yang diurutkan. 44 byte jika ASCII, 84 jika Unicode. Sebagai alternatif, perlakukan UPC sebagai int64 dan Anda mendapatkan 42 & 72 byte. 10.000 catatan - dalam kasus tertinggi Anda melihat sedikit di bawah penyimpanan megabyte.

Pendekatan O (1): Jangan menyimpan UPC, sebagai gantinya Anda menggunakannya sebagai entri ke dalam array. Dalam kasus terendah, Anda melihat hampir sepertiga terabyte penyimpanan.

Pendekatan mana yang Anda gunakan tergantung pada perangkat keras Anda. Pada sebagian besar konfigurasi modern yang masuk akal, Anda akan menggunakan pendekatan log N. Saya bisa membayangkan pendekatan kedua menjadi jawaban yang tepat jika karena alasan tertentu Anda berjalan di lingkungan di mana RAM sangat pendek tetapi Anda memiliki banyak penyimpanan massal. Sepertiga terabyte pada disk bukanlah masalah besar, mendapatkan data Anda dalam satu probe disk bernilai sesuatu. Pendekatan biner sederhana mengambil rata-rata 13. (Namun, perlu diketahui bahwa dengan mengelompokkan kunci Anda, Anda dapat memperoleh ini hingga 3 bacaan yang dijamin dan dalam praktiknya Anda akan men-cache yang pertama.)

Pertimbangkan pohon merah-hitam. Ini memiliki akses, pencarian, masukkan, dan hapus O(log n). Bandingkan dengan array, yang memiliki akses O(1)dan sisa operasi O(n).

Jadi mengingat aplikasi tempat kami menyisipkan, menghapus, atau mencari lebih sering daripada yang kami akses dan pilihan antara hanya dua struktur ini, kami lebih suka pohon merah-hitam. Dalam hal ini, Anda mungkin mengatakan kami lebih suka O(log n)waktu akses yang lebih rumit dari pohon merah-hitam .

Mengapa? Karena akses bukan urusan utama kami. Kami melakukan trade off: kinerja aplikasi kami lebih banyak dipengaruhi oleh faktor selain yang ini. Kami mengizinkan algoritme khusus ini untuk mengalami kinerja karena kami memperoleh keuntungan besar dengan mengoptimalkan algoritme lain.

Jadi jawaban untuk pertanyaan Anda hanyalah ini: ketika laju pertumbuhan algoritme bukan yang ingin kami optimalkan , ketika kami ingin mengoptimalkan sesuatu yang lain. Semua jawaban lain adalah kasus khusus ini. Terkadang kami mengoptimalkan waktu operasi yang lain. Terkadang kami mengoptimalkan memori. Terkadang kami mengoptimalkan keamanan. Terkadang kami mengoptimalkan perawatan. Terkadang kami mengoptimalkan waktu pengembangan. Bahkan konstanta utama yang cukup rendah untuk masalah adalah mengoptimalkan waktu berjalan ketika Anda tahu tingkat pertumbuhan algoritma bukan dampak terbesar pada waktu berjalan. (Jika kumpulan data Anda berada di luar rentang ini, Anda akan mengoptimalkan untuk tingkat pertumbuhan algoritma karena pada akhirnya akan mendominasi konstanta.) Semuanya memiliki biaya, dan dalam banyak kasus, kami menukar biaya dengan tingkat pertumbuhan yang lebih tinggi untuk algoritma untuk mengoptimalkan sesuatu yang lain.

Iya.

Dalam kasus nyata, kami menjalankan beberapa tes untuk melakukan pencarian tabel dengan kedua kunci string pendek dan panjang.

Kami menggunakan std::map, std::unordered_mapdengan hash yang sampel paling banyak 10 kali dari panjang string (kunci kami cenderung seperti panduan, jadi ini layak), dan hash yang sampel setiap karakter (secara teori mengurangi tabrakan), vektor yang tidak disortir tempat kami melakukan ==perbandingan, dan (jika saya ingat dengan benar) vektor yang tidak disortir tempat kami juga menyimpan hash, pertama-tama membandingkan hash, kemudian membandingkan karakter.

Algoritma ini berkisar dari O(1)(unordered_map) hingga O(n)(pencarian linear).

Untuk N berukuran sedang, cukup sering O (n) mengalahkan O (1). Kami menduga ini karena kontainer berbasis node mengharuskan komputer kami untuk melompat-lompat di memori lebih banyak, sedangkan kontainer berbasis linear tidak.

O(lg n)ada di antara keduanya. Saya tidak ingat bagaimana itu terjadi.

Perbedaan kinerja tidak terlalu besar, dan pada set data yang lebih besar, hash berbasis melakukan jauh lebih baik. Jadi kami terjebak dengan peta unordered berbasis hash.

Dalam prakteknya, untuk n ukuran yang wajar, O(lg n)adalah O(1). Jika komputer Anda hanya memiliki ruang untuk 4 miliar entri di tabel Anda, maka O(lg n)dibatasi oleh 32. (lg (2 ^ 32) = 32) (dalam ilmu komputer, lg adalah kependekan dari log 2).

Dalam prakteknya, algoritma lg (n) lebih lambat daripada algoritma O (1) bukan karena faktor pertumbuhan logaritmik, tetapi karena bagian lg (n) biasanya berarti ada tingkat kompleksitas tertentu pada algoritma, dan kompleksitas menambahkan faktor konstan yang lebih besar daripada "pertumbuhan" apa pun dari istilah lg (n).

Namun, algoritma O (1) yang kompleks (seperti pemetaan hash) dapat dengan mudah memiliki faktor konstan yang sama atau lebih besar.

Kemungkinan untuk mengeksekusi suatu algoritma secara paralel.

Saya tidak tahu apakah ada contoh untuk kelas O(log n)dan O(1), tetapi untuk beberapa masalah, Anda memilih algoritma dengan kelas kompleksitas yang lebih tinggi ketika algoritma lebih mudah dieksekusi secara paralel.

Beberapa algoritma tidak dapat diparalelkan tetapi memiliki kelas kompleksitas yang sangat rendah. Pertimbangkan algoritma lain yang mencapai hasil yang sama dan dapat diparalelkan dengan mudah, tetapi memiliki kelas kompleksitas yang lebih tinggi. Ketika dieksekusi pada satu mesin, algoritma kedua lebih lambat, tetapi ketika dieksekusi pada beberapa mesin, waktu eksekusi yang sebenarnya semakin rendah dan lebih rendah sedangkan algoritma pertama tidak dapat mempercepat.

Katakanlah Anda menerapkan daftar hitam pada sistem tertanam, di mana angka antara 0 dan 1.000.000 mungkin masuk daftar hitam. Itu membuat Anda dua opsi yang mungkin:

1. Gunakan bitet 1.000.000 bit
2. Gunakan array yang diurutkan dari bilangan bulat daftar hitam dan gunakan pencarian biner untuk mengaksesnya

Akses ke bitset akan menjamin akses konstan. Dalam hal kompleksitas waktu, itu optimal. Baik dari sudut pandang teoritis maupun praktis (itu adalah O (1) dengan overhead konstan yang sangat rendah).

Namun, Anda mungkin ingin memilih solusi kedua. Terutama jika Anda mengharapkan jumlah bilangan bulat daftar hitam menjadi sangat kecil, karena akan lebih hemat memori.

Dan bahkan jika Anda tidak mengembangkan untuk sistem tertanam di mana memori langka, saya hanya dapat meningkatkan batas sewenang-wenang dari 1.000.000 menjadi 1.000.000.000.000 dan membuat argumen yang sama. Maka bitet akan membutuhkan sekitar 125G memori. Memiliki kompleksitas kasus terburuk yang dijamin dari O (1) mungkin tidak meyakinkan atasan Anda untuk memberi Anda server yang kuat.

Di sini, saya lebih suka pencarian biner (O (log n)) atau pohon biner (O (log n)) daripada bitet O (1). Dan mungkin, tabel hash dengan kompleksitas kasus terburuknya O (n) akan mengalahkan mereka semua dalam praktik.

Jawaban saya di sini Pilihan cepat acak tertimbang di semua baris matriks stokastik adalah contoh di mana algoritma dengan kompleksitas O (m) lebih cepat daripada yang dengan kompleksitas O (log (m)), ketika mtidak terlalu besar.

Orang-orang sudah menjawab pertanyaan persis Anda, jadi saya akan menjawab pertanyaan yang sedikit berbeda yang mungkin dipikirkan orang ketika datang ke sini.

Banyak "O (1) waktu" algoritma dan struktur data sebenarnya hanya mengambil diharapkan O (1) waktu, yang berarti bahwa mereka rata-rata waktu berjalan adalah O (1), mungkin hanya di bawah asumsi tertentu.

Contoh umum: hashtable, perluasan "daftar array" (alias array / vektor berukuran dinamis).

Dalam skenario seperti itu, Anda mungkin lebih suka menggunakan struktur data atau algoritma yang waktunya dijamin secara absolut terikat secara logaritma, meskipun rata-rata kinerjanya lebih buruk.
Contoh karena itu mungkin pohon pencarian biner seimbang, yang waktu berjalannya lebih buruk rata-rata tetapi lebih baik dalam kasus terburuk.

Sebuah pertanyaan yang lebih umum adalah jika ada situasi di mana satu akan lebih memilih O(f(n))algoritma untuk sebuah O(g(n))algoritma meskipun g(n) << f(n)sebagai ncenderung tak terbatas. Seperti yang telah disebutkan orang lain, jawabannya jelas "ya" dalam kasus di mana f(n) = log(n)dan g(n) = 1. Kadang-kadang ya bahkan dalam kasus yang f(n)jumlahnya banyak tetapi g(n)eksponensial. Contoh terkenal dan penting adalah Algoritma Simplex untuk memecahkan masalah pemrograman linier. Pada 1970-an itu terbukti O(2^n). Dengan demikian, perilaku terburuknya tidak mungkin terjadi. Tapi - rata - rata perilaku kasusnya sangat baik, bahkan untuk masalah praktis dengan puluhan ribu variabel dan kendala. Pada 1980-an, algoritma waktu polinomial (seperti aAlgoritma interior-point Karmarkar) untuk pemrograman linier ditemukan, tetapi 30 tahun kemudian algoritma simpleks tampaknya masih menjadi algoritma pilihan (kecuali untuk masalah yang sangat besar tertentu). Ini adalah alasan yang jelas bahwa perilaku kasus-rata sering lebih penting daripada perilaku kasus-buruk, tetapi juga untuk alasan yang lebih halus bahwa algoritma simpleks dalam beberapa hal lebih informatif (misalnya informasi sensitivitas lebih mudah untuk diekstraksi).

Untuk memasukkan 2 sen saya ke:

Kadang-kadang algoritma kompleksitas yang lebih buruk dipilih sebagai pengganti algoritma yang lebih baik, ketika algoritma tersebut berjalan pada lingkungan perangkat keras tertentu. Misalkan algoritma O (1) kami non-berurutan mengakses setiap elemen dari array berukuran sangat besar untuk menyelesaikan masalah kami. Kemudian letakkan array itu pada hard drive mekanis, atau pita magnetik.

Dalam hal itu, algoritma O (logn) (misalkan mengakses disk secara berurutan), menjadi lebih menguntungkan.

Ada kasus penggunaan yang baik untuk menggunakan algoritma O (log (n)) alih-alih algoritma O (1) yang telah diabaikan oleh banyak jawaban lainnya: immutability. Peta hash memiliki O (1) menempatkan dan mendapatkan, dengan asumsi distribusi nilai hash yang baik, tetapi mereka membutuhkan keadaan bisa berubah. Peta pohon yang tidak dapat berubah memiliki O (log (n)) menempatkan dan mendapatkan, yang secara asimptot lebih lambat. Namun, ketidakmampuan dapat cukup berharga untuk menebus kinerja yang lebih buruk dan dalam kasus di mana beberapa versi peta perlu dipertahankan, kekekalan memungkinkan Anda untuk menghindari keharusan menyalin peta, yaitu O (n), dan karenanya dapat meningkatkan kinerja.

Cukup: Karena koefisien - biaya yang terkait dengan pengaturan, penyimpanan, dan waktu pelaksanaan langkah itu - bisa jauh lebih besar dengan masalah big-O yang lebih kecil daripada dengan yang lebih besar. Big-O hanya ukuran skalabilitas algoritma .

Pertimbangkan contoh berikut dari Kamus Peretas, yang mengusulkan algoritme pengurutan bergantung pada Multiple Worlds Interpretation of Quantum Mechanics :

1. Izinkan array secara acak menggunakan proses kuantum,
2. Jika array tidak diurutkan, hancurkan jagat raya.
3. Semua alam semesta yang tersisa sekarang disortir [termasuk yang ada di dalamnya].

(Sumber: http://catb.org/~esr/jargon/html/B/bogo-sort.html )

Perhatikan bahwa big-O dari algoritme ini adalah O(n), yang mengalahkan algoritma penyortiran yang dikenal hingga saat ini pada item umum. Koefisien langkah linear juga sangat rendah (karena ini hanya perbandingan, bukan swap, yang dilakukan secara linear). Algoritme yang sama dapat, pada kenyataannya, digunakan untuk memecahkan masalah dalam NP dan co-NP dalam waktu polinomial, karena setiap solusi yang mungkin (atau bukti yang mungkin bahwa tidak ada solusi) dapat dihasilkan menggunakan proses kuantum, kemudian diverifikasi dalam waktu polinomial.

Namun, dalam kebanyakan kasus, kita mungkin tidak ingin mengambil risiko bahwa Multiple Worlds mungkin tidak benar, belum lagi bahwa tindakan menerapkan langkah 2 masih "dibiarkan sebagai latihan untuk pembaca".

Pada titik mana pun ketika n dibatasi dan pengali konstan algoritma O (1) lebih tinggi daripada batas pada log (n). Misalnya, menyimpan nilai dalam hashset adalah O (1), tetapi mungkin memerlukan perhitungan mahal dari fungsi hash. Jika item data dapat dibandingkan secara sepele (sehubungan dengan beberapa urutan) dan ikatan n adalah sedemikian sehingga log n secara signifikan lebih kecil dari perhitungan hash pada salah satu item, maka menyimpan dalam pohon biner seimbang mungkin lebih cepat daripada menyimpan dalam hashset.

Dalam situasi realtime di mana Anda memerlukan batas atas perusahaan Anda akan memilih misalnya heapsort sebagai lawan dari Quicksort, karena perilaku rata-rata heapsort juga perilaku terburuknya.

Menambah jawaban yang sudah bagus. Contoh praktisnya adalah indeks Hash vs indeks B-tree dalam database postgres.

Indeks hash membentuk indeks tabel hash untuk mengakses data pada disk sementara btree seperti namanya menggunakan struktur data Btree.

Dalam waktu Big-O ini adalah O (1) vs O (logN).

Indeks hash saat ini tidak dianjurkan dalam postgres karena dalam situasi kehidupan nyata khususnya dalam sistem database, mencapai hashing tanpa tabrakan sangat sulit (dapat menyebabkan O (N) kompleksitas kasus terburuk) dan karena ini, bahkan lebih sulit untuk membuat mereka macet aman (disebut write ahead logging - WAL in postgres).

Pengorbanan ini dibuat dalam situasi ini karena O (logN) cukup baik untuk indeks dan menerapkan O (1) cukup sulit dan perbedaan waktu tidak terlalu menjadi masalah.

Ketika nkecil, dan O(1)selalu lambat.

1. Ketika unit kerja "1" di O (1) sangat tinggi relatif terhadap unit kerja di O (log n) dan ukuran set yang diharapkan adalah kecil. Sebagai contoh, mungkin lebih lambat untuk menghitung kode hash Kamus daripada iterate array jika hanya ada dua atau tiga item.

atau

2. Ketika memori atau kebutuhan sumber daya non-waktu lainnya dalam algoritma O (1) sangat besar relatif terhadap algoritma O (log n).

1. ketika mendesain ulang suatu program, prosedur ditemukan dioptimalkan dengan O (1) bukan O (lgN), tetapi jika itu bukan hambatan dari program ini, dan sulit untuk memahami O (1) alg. Maka Anda tidak perlu menggunakan algoritma O (1)
2. ketika O (1) membutuhkan banyak memori yang tidak dapat Anda pasok, sementara waktu O (lgN) dapat diterima.

Hal ini sering terjadi pada aplikasi keamanan yang ingin kita rancang masalah yang algoritmanya lambat dengan sengaja untuk menghentikan seseorang dari mendapatkan jawaban atas masalah terlalu cepat.

Berikut adalah beberapa contoh dari atas kepala saya.

• Pembuatan kata sandi kadang-kadang dibuat lambat secara acak untuk mempersulit menebak kata sandi dengan kekerasan. Pos Keamanan Informasi ini memiliki poin-poin tentang hal itu (dan banyak lagi).
• Koin Bit menggunakan masalah lambat yang terkendali untuk jaringan komputer untuk memecahkan untuk "menambang" koin. Ini memungkinkan mata uang ditambang pada tingkat yang dikendalikan oleh sistem kolektif.
• Cipher asimetris (seperti RSA ) dirancang untuk membuat dekripsi tanpa kunci yang sengaja lambat untuk mencegah orang lain tanpa kunci pribadi untuk memecahkan enkripsi. Algoritma ini dirancang untuk di-crack semoga dalam O(2^n)waktu di mana nbit-length dari kunci (ini adalah brute force).

Di tempat lain di CS, Sortir Cepat O(n^2)dalam kasus terburuk tetapi dalam kasus umum adalah O(n*log(n)). Untuk alasan ini, analisis "Big O" terkadang bukan satu-satunya hal yang Anda pedulikan ketika menganalisis efisiensi algoritma.