Bagaimana cara menemukan waktu berjalan berdasarkan kecepatan algoritma dan kecepatan komputer?

Saat ini saya sedang mengerjakan tugas yang berhubungan dengan Big-O dan waktu berjalan. Saya mempunyai satu pertanyaan yang tampaknya sangat mudah, tetapi saya tidak yakin apakah saya melakukannya dengan benar. Soal-soal lainnya cukup sulit, dan saya merasa ada sesuatu yang terlewatkan di sini.

Pertama, Anda memiliki hal-hal ini: Algoritma A, yang memiliki waktu berjalan 50n^3. Komputer A yang memiliki kecepatan 1 milidetik per operasi. Komputer B yang memiliki kecepatan 2 milidetik per operasi. Contoh ukuran 300.

Saya ingin mengetahui berapa lama waktu yang dibutuhkan algoritma A untuk menyelesaikan masalah ini di komputer A, dan berapa lama waktu yang dibutuhkan di komputer B.

Yang ingin saya lakukan adalah sub 300 in untuk n, jadi Anda memiliki 50*(300^2) = 4500000.

Lalu kalikan dengan 1 untuk komputer pertama dan 2 untuk komputer kedua.

Ini terasa aneh bagi saya, karena dikatakan "waktu berjalan" adalah 50n^3, bukan, "jumlah operasinya adalah 50n^3", jadi saya merasa bahwa saya mengalikan waktu dengan waktu, dan akankah berakhir dengan satuan milidetik kuadrat, yang sepertinya tidak tepat sama sekali.

Saya ingin tahu apakah saya benar, dan jika tidak, apa sebenarnya maksud pertanyaan tersebut.


performance complexity-theory
person Zachary Wright    schedule 19.10.2008    source sumber
comment
Hanya ingin menunjukkan bahwa Anda beralih dari 50n^3 dalam deskripsi, menjadi 50n^2 dalam perhitungan Anda. Tentu saja, hal itu membuat perbedaan besar pada hasil yang Anda peroleh.   -  person Mark Bessey    schedule 23.10.2008

Jawaban (3)


arrow_upward
2
arrow_downward

Tidak masuk akal jika Anda memiliki O(n^3) tetapi Anda tidak menggunakan notasi O besar dalam contoh Anda. Yaitu. jika Anda memiliki O(n^3) Anda akan mengetahui kompleksitas algoritme Anda tetapi Anda tidak akan mengetahui jumlah pasti operasi seperti yang Anda katakan.

Sebaliknya sepertinya Anda diberi jumlah pasti operasi yang dilakukan. (Bahkan ketahuilah itu tidak disebutkan secara eksplisit). Jadi mengganti n akan masuk akal.

Notasi O Besar menjelaskan bagaimana ukuran input akan mempengaruhi waktu berjalan atau penggunaan memori Anda. Namun dengan Big O Anda tidak dapat menyimpulkan waktu pengoperasian yang tepat meskipun mengingat kecepatan setiap pengoperasian.

Memberikan penjelasan mengapa jawaban Anda terlihat begitu sederhana (seperti yang saya jelaskan di atas) juga merupakan cara yang aman. Tapi saya yakin bahkan tanpa itu Anda akan mendapat nilai untuk pertanyaan itu.

person Brian R. Bondy    schedule 19.10.2008

arrow_upward
1
arrow_downward

Ya, selain tidak ada gunanya mencari tahu berapa lama sesuatu akan berlangsung seperti ini pada sebagian besar komputer modern, meskipun mungkin memiliki beberapa arti dalam sistem tertanam, bagi saya hal itu terlihat benar seperti yang Anda lakukan. dia.

Jika algoritme memerlukan 50n^3 operasi untuk menyelesaikan sesuatu, di mana n adalah jumlah elemen yang akan diproses, maka mengganti n dengan 300 akan memberi Anda jumlah operasi yang harus dilakukan, bukan satuan waktu.

Jadi kalikan dengan waktu per operasi dan Anda akan mendapatkan waktu yang dibutuhkan.

Tampak tepat bagi saya.

person Lasse V. Karlsen    schedule 19.10.2008

arrow_upward
0
arrow_downward

Data 50*n^3 Anda disebut "waktu berjalan", tetapi itu karena model yang digunakan untuk evaluasi kecepatan mengasumsikan mesin dengan beberapa operasi dasar, yang masing-masing memerlukan 1 unit waktu.

Dalam kasus Anda, menjalankan algoritme membutuhkan 50*500^3 unit waktu. Di komputer A setiap satuannya adalah 1 ms, dan di komputer B 2 ms.

Semoga ini memberi pemahaman pada unitnya,
Asaf.

person Asaf R    schedule 19.10.2008