Perbedaan antara kompleksitas waktu dan kompleksitas komputasi

Untuk mengukur kompleksitas suatu algoritma, apakah itu kompleksitas waktu, atau kompleksitas komputasi? Apa perbedaan di antara mereka?

Saya biasa menghitung jumlah maksimum (terburuk) operasi dasar (paling mahal) dalam algoritma.

complexity-theory terminology algorithm-analysis time-complexity Median Hilal
sumber

Bukan jawaban untuk pertanyaan Anda, tetapi karena minat Anda pada hal semacam ini, Anda mungkin juga tertarik pada cs.stackexchange.com/q/13669/755

"kompleksitas suatu algoritma" ketika mengacu pada runime asimptotik adalah istilah yang keliru (sering digunakan). Anda ingin mengatakan "runtime asimptotik".

Raphael

Jawaban:

Kompleksitas komputasi hanyalah istilah yang lebih umum, karena waktu bukanlah satu-satunya sumber yang ingin kita pertimbangkan. Yang paling jelas berikutnya adalah ruang yang digunakan algoritma, dan karenanya kita dapat berbicara tentang kompleksitas ruang , juga sebagai bagian dari kompleksitas komputasi. Memang kita bisa melakukan ini untuk ukuran apa pun yang Anda inginkan Anda gunakan, tentu saja beberapa tindakan lebih berguna daripada yang lain.

Jadi menghitung jumlah langkah yang diambil algoritma dalam kasus terburuk memberikan kompleksitas waktu terikat untuk masalah yang dipecahkannya, menghitung berapa banyak memori / berapa banyak sel sel yang digunakannya memberikan kompleksitas ruang terikat dll. Dll.

$P$ $\mathsf{Sorting}$ $P$ $O(n\log n)$ $\mathsf{Sorting}$ $TC^{0}$ $AC^{0}$

Luke Mathieson
sumber

@shekharsuman Dengan masalah yang saya maksud adalah gagasan formal tentang masalah komputasi (mis. k-Vertex Cover), bukan arti umum. Kompleksitas komputasi adalah klasifikasi masalah komputasi, jadi dalam pengertian formal, kompleksitas merujuk pada apa yang dapat kita katakan tentang masalah tersebut. Hasil tentang algoritme memberi tahu kami hal-hal tentang kerumitan masalah, tetapi tidak dengan sendirinya hasil kompleksitas (tetapi secara informal kami berbicara tentang kompleksitas suatu algoritma).

Luke Mathies

@shekharsuman paragraf pembuka halaman wikipedia adalah ringkasan yang cukup bagus.

Luke Mathies

@ Lukas Terima kasih, ini membuat semuanya menjadi jelas. Namun, jika saya dapat menggunakan idiom "jenis kompleksitas yang paling banyak digunakan untuk secara formal mengevaluasi algoritma" (Meskipun saya tahu ini tidak tepat). Apa itu waktu vs komputasi? Apa yang saya pikirkan adalah bahwa, secara umum, yang paling penting adalah waktu, karena sumber daya lebih dapat diperluas dalam beberapa hal!

Median Hilal

@MedianHilal time memang ukuran yang paling umum dipertimbangkan untuk kompleksitas masalah. Ruang tidak terlalu jauh di belakang (setidaknya oleh teoretikus kompleksitas, dan orang yang berurusan dengan dataset sangat besar, kurang begitu sehari-hari).

Luke Mathies

-2

Kompleksitas siklomatik sering digunakan sebagai ukuran kompleksitas komputasi, contoh yang berguna disediakan di /programming/9097987/calculation-of-cyclomatic-complexity

Mungkin ada banyak jalur (mungkin bersarang) yang berbeda melalui algoritma yang memberikannya kompleksitas siklomatik yang tinggi, tetapi tidak ada loop yang memberikan kompleksitas waktu yang rendah. Suatu program dengan satu loop akan memiliki kompleksitas siklomatik yang rendah tetapi mungkin kompleksitas waktu yang tinggi.

Kompleksitas siklus sering digunakan sebagai ukuran pemeliharaan yang diperlukan untuk kode. Diskusi yang lebih terperinci disediakan di http://docs.sonarqube.org/display/SONAR/Bad+Distribution+of+Complexity . Ini berbeda dengan kompleksitas waktu yang menjalankan pengukuran waktu dari kode dan dapat digunakan untuk menilai persepsi pengguna tentang efektivitas sistem.

seperti beludru
sumber

Pertanyaannya adalah tentang kompleksitas komputasi, bukan tentang kompleksitas siklomatik!

Am_I_Helpful

Anda mungkin ingin membaca OP - dia bertanya tentang kompleksitas suatu algoritma - Kompleksitas siklus memberikan ukuran statis dari kompleksitas algoritma komputasi - coba tambahkan umpan balik positif waktu berikutnya

velvetytoast

Kompleksitas siklus tidak mengukur kompleksitas komputasi. Kompleksitas komputasi mengacu pada waktu berjalan, bukan seberapa rumit struktur kode sumber.

@DW Secara lebih akurat, kompleksitas komputasi mengacu pada sumber daya yang diperlukan untuk menyelesaikan masalah (yang mungkin termasuk ruang, pergantian, panggilan oracle dan sebagainya, serta waktu).

David Richerby

@ DavidRicherby Saya bukan ahli dalam hal ini, jadi mohon koreksi jika salah. Ukuran kompleksitas statis, seperti ukuran program memang berperan dalam beberapa situasi. Apakah saya benar bahwa itu lebih terkait dengan kompleksitas Kolmogorov. Apakah itu juga menjadi masalah bagi kompleksitas Siklomatik? Satu jenis kompleksitas untuk menulis program atau masalah, dan yang lain untuk memecahkan atau menjalankannya ... mungkin perkiraan singkat dari situasi tersebut. Saya tidak yakin saya akan menulis pertanyaan yang masuk akal tentang ini.

babou