Permintaan maaf untuk pertanyaan pemula, tapi saya agak bingung tentang apa yang sebenarnya dianggap sebagai "operasi sederhana" ketika menghitung kompleksitas waktu dari suatu algoritma. Secara khusus, mengapa kita menganggap semua operasi sama?
Tentunya, membagi dua angka yang sangat besar lebih memakan waktu daripada menambahkan satu ke nomor (seperti dalam setiap iterasi dari for for loop). Perkalian, misalnya, dapat terdiri dari sejumlah penambahan kecil. Jadi, alih-alih hanya menambahkannya, bukankah kita harus menerapkan semacam bobot untuk setiap operasi tergantung pada jenis operasi (penambahan, perkalian, dll.) Dan ukuran angka yang terlibat?
Masalah saya adalah saya diminta untuk membuktikan bahwa kompleksitas algoritma saya adalah (untuk beberapa fungsi ) dan saya tidak yakin bagaimana melakukan ini dengan cara yang ketat secara matematis karena ketidakjelasan yang melekat dalam definisi sebuah "operasi sederhana". Jadi bagaimana saya akan melakukan ini?
sumber
Jawaban:
Operasi sederhana adalah segala sesuatu yang membutuhkan waktu konstan untuk dicapai. Kebingungannya adalah bahwa pembagian tampaknya tidak memakan waktu yang konstan, dan pada kenyataannya, secara umum tidak. TAPI!
Pembagian dan penambahan keduanya membutuhkan waktu konstan jika, katakanlah, Anda menambahkan dua bilangan bulat 32-bit bersama, yang biasanya seperti itu. Namun, jika Anda menambahkan angka besar secara sewenang-wenang, mereka tidak akan benar-benar menjadi waktu konstan, meskipun kadang-kadang saya pikir orang akan memperlakukannya seolah-olah itu karena angkanya dianggap tidak menjadi super besar.
sumber