Saya sedang mempelajari kursus Coursera tentang kompleksitas waktu. Saya menemukan ini di video dan saya pikir ada sesuatu yang salah. “Jadi misalkan kita mempunyai suatu algoritma yang runtimenya kira-kira sebanding dengan n dan kita ingin algoritma tersebut dijalankan pada mesin yang berjalan pada kecepatan sekitar satu gigahertz. Berapa besar input yang dapat kita tangani sehingga kita dapat menyelesaikan perhitungannya dalam hitungan detik ? ” (CPU 1GHZ (10^9 siklus per detik))
“Jika dijalankan pada ukuran n, Anda dapat menangani sekitar satu miliar input berukuran, sebelum dibutuhkan lebih dari satu detik” (10^9 / 10^9)
“Jika berjalan seperti n kuadrat, itu jauh lebih buruk. Anda hanya dapat menangani input berukuran sekitar 30.000 sebelum mulai memakan waktu lebih dari satu detik.” n = 30000, (30000)^2/10^9 = 0,9 detik ~ 1 detik
“Jika input berukuran 2 hingga n, itu sangat buruk, Anda hanya dapat menangani input berukuran sekitar 30 dalam satu detik” 2^30/10^9 ~ 1,07 detik
Dengan kompleksitas n log(n), jika ukuran input n adalah 10^9, maka dibutuhkan waktu 10^9 * log(10^9) / 10^9 = 9 detik, bukan? Entah bagaimana itu menunjukkan 30 detik dalam video. Dikatakan juga bahwa jika n = 10^7.5 maka runtimenya adalah 1 detik, yang juga salah dengan perhitungan saya.
Saya menghitung setiap kasus dengan kompleksitas n, n^2, 2^n dan semuanya benar, hanya kasus nlog(n) yang kacau
Berikut fotonya untuk lebih jelasnya: https://i.upanh.org/2022/04/11/nlogn.jpg[^]
Menautkan video kursus (3:40 hingga 5:00 adalah bagiannya): https://www.coursera.org/lecture/algorithmic-toolbox/asymptotic-notation-zI8dH[^]
Saya mengedit pertanyaannya sehingga seperti di video kursus yang saya tonton
Apa yang saya coba:
I calculated every case with the n, n^2, 2^n complexity and everything was right, only nlog(n) case messed up
Solusi 1
Mengutip:Jika ukuran input n adalah 10^9, maka perlu waktu 10^9 * log(10^9) / 10^9 = 9 detik, bukan?
TIDAK ! Anda tidak menghitung runtime dari notasi Big O, setidaknya tidak dengan sendirinya.
Notasi Big O memberi tahu Anda kompleksitas kategori suatu algoritma, bukan runtime, tidak secara langsung.
Saat Anda memiliki waktu proses untuk ukuran data tertentu, kompleksitas Big O memungkinkan Anda mengevaluasi waktu proses untuk ukuran data lainnya.
waktu Anda 1 detik untuk data dari 20 hingga 10^6 berarti Anda perlu beralih ke waktu milidetik untuk mendapatkan waktu yang bermakna.
Solusi 2
Besar O tidak memberikan waktu pelaksanaan yang tepat. Lihat, misalnya Notasi O Besar – Wikipedia[^] (Properti bagian, perkalian dengan konstanta).
Solusi 3
Untuk menambah apa yang dikatakan orang lain, Anda tidak dapat menyamakan siklus jam secara langsung dengan waktu eksekusi – beberapa operasi mesin memerlukan n siklus untuk dieksekusi, yang lain mungkin n * 2. Selain itu, prosesor modern disalurkan – jadi beberapa instruksi dapat dimulai ketika instruksi lain sedang dieksekusi, di-cache – jadi waktu eksekusi mungkin bergantung pada berapa lama instruksi terakhir dieksekusi dan apakah datanya tersedia dalam cache L1, L2 atau L3, ketersediaan inti bebas untuk dieksekusi, ‘ditambah sejumlah lainnya detail.
Anda tidak bisa hanya mengatakan “kecepatan jam saya X, jadi waktu eksekusi saya X * Y” – ada terlalu banyak faktor lain yang akan mempengaruhinya.
Solusi 5
30 detik adalah waktu yang tepat jika itu log2(N). catatan2(1000) ~= 10.
Sunting: Algoritme O(n log(n)) sering kali membagi masalah menjadi dua secara rekursif, menyelesaikan setiap bagian secara terpisah, dan kemudian menggabungkan solusinya. Inilah sebabnya mengapa log2 biasanya tersirat. Mergesort adalah contoh yang bagus.
Solusi 6
notasi O besar hanya memberitahu Anda bagaimana waktu eksekusinya mengubah ketika “ukuran” masalah diubah, hal ini tidak memberikan perkiraan aktual untuk kasus tertentu.
Dengan kata lain, ada faktor yang tidak diketahui, misalnya O(n2) bisa berarti
time_needed = constant * n * n
di mana tidak ada yang tahu berapa nilai konstanta tersebut, maka tidak ada nilai konkret untuk waktu_yang dibutuhkan.
Contoh ini hanya memberi tahu Anda bahwa masalah yang dua kali lebih besar akan memerlukan waktu empat kali lebih lama untuk diselesaikan.
コメント