[Powered by Google Translate] Anda mungkin pernah mendengar orang berbicara tentang algoritma cepat atau efisien
untuk melaksanakan tugas tertentu Anda,
tapi apa sebenarnya artinya untuk algoritma untuk menjadi cepat atau efisien?
Nah, itu tidak berbicara tentang pengukuran secara real time,
seperti detik atau menit.
Hal ini karena perangkat keras komputer
dan perangkat lunak bervariasi secara drastis.
Program saya bisa berjalan lebih lambat dari Anda,
karena aku menjalankannya pada komputer yang lebih tua,
atau karena saya kebetulan bermain game video online
pada saat yang sama, yang memonopoli semua memori saya,
atau aku mungkin menjalankan program saya melalui perangkat lunak yang berbeda
yang berkomunikasi dengan mesin berbeda pada tingkat yang rendah.
Ini seperti membandingkan apel dan jeruk.
Hanya karena komputer saya lambat memakan waktu lebih lama
dari Anda untuk memberikan kembali jawaban
tidak berarti Anda memiliki algoritma yang lebih efisien.
>> Jadi, karena kita tidak bisa langsung membandingkan runtimes program
dalam hitungan detik atau menit,
bagaimana kita membandingkan 2 algoritma yang berbeda
terlepas dari hardware atau lingkungan perangkat lunak?
Untuk membuat cara yang lebih seragam untuk mengukur efisiensi algoritmik,
ilmuwan komputer dan matematika telah menyusun
konsep untuk mengukur kompleksitas asimtotik dari program
dan notasi yang disebut 'Ohnotation Big'
untuk menggambarkan hal ini.
Definisi formal adalah bahwa fungsi f (x)
berjalan pada urutan g (x)
jika ada beberapa nilai (x), x dan ₀
beberapa konstan, C, yang
f (x) adalah kurang dari atau sama dengan
bahwa kali konstanta g (x)
untuk semua x lebih besar daripada x ₀.
>> Tapi jangan takut pergi oleh definisi formal.
Apakah ini benar-benar berarti dalam waktu kurang istilah teoritis?
Yah, itu pada dasarnya cara menganalisis
seberapa cepat runtime program ini tumbuh asimtotik.
Artinya, sebagai ukuran masukan Anda meningkat menuju tak terhingga,
mengatakan, Anda sedang menyortir sebuah array ukuran 1.000 dibandingkan dengan array ukuran 10.
Bagaimana runtime program Anda tumbuh?
Sebagai contoh, bayangkan menghitung jumlah karakter
dalam sebuah string cara paling sederhana
dengan berjalan melalui seluruh string
Surat-by-surat dan menambahkan 1 ke counter untuk setiap karakter.
Algoritma ini dikatakan berjalan dalam waktu linear
sehubungan dengan jumlah karakter,
'N' dalam string.
Singkatnya, berjalan di O (n).
Mengapa ini?
Nah, dengan menggunakan pendekatan ini, waktu yang diperlukan
untuk melintasi seluruh string
sebanding dengan jumlah karakter.
Menghitung jumlah karakter dalam string 20-karakter
akan mengambil dua kali lebih lama yang dibutuhkan
untuk menghitung karakter dalam string 10-karakter,
karena Anda harus melihat semua karakter
dan karakter masing-masing mengambil jumlah waktu yang sama untuk melihat.
Seperti Anda meningkatkan jumlah karakter,
runtime akan meningkat secara linear dengan panjang input.
>> Sekarang, bayangkan jika Anda memutuskan bahwa waktu linier,
O (n), hanya tidak cukup cepat untuk Anda?
Mungkin Anda menyimpan string besar,
dan Anda tidak dapat membayar waktu tambahan itu akan mengambil
untuk melintasi semua karakter mereka menghitung satu-per-satu.
Jadi, Anda memutuskan untuk mencoba sesuatu yang berbeda.
Bagaimana jika Anda akan terjadi sudah menyimpan jumlah karakter
dalam string, misalnya, dalam sebuah variabel yang disebut 'len,'
pada awal program,
bahkan sebelum Anda menyimpan karakter pertama dalam string Anda?
Kemudian, semua yang Anda harus lakukan sekarang untuk mengetahui panjang string,
adalah memeriksa apa nilai variabel tersebut.
Anda tidak perlu melihat string itu sendiri sama sekali,
dan mengakses nilai dari variabel seperti len dianggap
operasi asimtotik konstan waktu,
atau O (1).
Mengapa ini? Nah, mengingat apa kompleksitas asimtotik berarti.
Bagaimana perubahan runtime sebagai ukuran
masukan dari Anda tumbuh?
>> Katakanlah Anda sedang mencoba untuk mendapatkan jumlah karakter dalam string yang lebih besar.
Yah, itu tidak akan peduli seberapa besar Anda membuat string,
bahkan satu juta karakter,
semua yang Anda harus lakukan untuk menemukan panjang string dengan pendekatan ini,
adalah untuk membaca nilai dari variabel len,
Anda yang sudah dibuat.
Panjang masukan, yaitu panjang string Anda mencoba untuk menemukan,
tidak mempengaruhi sama sekali seberapa cepat program Anda berjalan.
Ini bagian dari program anda akan berjalan sama cepat pada tali satu karakter
dan string seribu karakter,
dan itulah mengapa program ini akan disebut sebagai berjalan dalam waktu yang konstan
sehubungan dengan ukuran input.
>> Tentu saja, ada kelemahan.
Anda menghabiskan ruang memori tambahan pada komputer Anda
menyimpan variabel
dan waktu tambahan yang diperlukan Anda
untuk melakukan penyimpanan sebenarnya dari variabel,
tapi intinya masih berdiri,
mencari tahu berapa lama string Anda adalah
tidak tergantung pada panjang dari string sama sekali.
Jadi, itu berjalan dalam O (1) atau waktu konstan.
Hal ini tentu tidak harus berarti
bahwa kode Anda berjalan dalam 1 langkah,
tetapi tidak peduli berapa banyak langkah itu,
jika tidak berubah dengan ukuran input,
itu masih asimtotik konstan yang kami hadirkan sebagai O (1).
>> Seperti yang Anda mungkin bisa menebak,
ada banyak yang berbeda runtimes O besar untuk mengukur algoritma dengan.
O (n) ² algoritma asimtotik lebih lambat dari O (n) algoritma.
Artinya, sebagai jumlah elemen (n) tumbuh,
akhirnya O (n) ² algoritma akan memakan waktu lebih
dari O (n) algoritma untuk menjalankan.
Ini tidak berarti O (n) algoritma selalu berjalan lebih cepat
dari O (n) algoritma ², bahkan di lingkungan yang sama,
pada hardware yang sama.
Mungkin untuk ukuran masukan kecil,
O (n) ² algoritma mungkin benar-benar bekerja lebih cepat,
namun, pada akhirnya, sebagai ukuran input meningkat
menuju tak terhingga, O (n) runtime ² algoritma
akhirnya akan gerhana runtime dari algoritma (n) O.
Sama seperti fungsi matematika kuadrat
akhirnya akan menyalip setiap fungsi linear,
tidak peduli berapa banyak kepala mulai fungsi linear dimulai dengan.
Jika Anda bekerja dengan data dalam jumlah besar,
algoritma yang berjalan di O (n) ² waktu benar-benar dapat berakhir memperlambat program Anda,
tapi untuk ukuran masukan kecil,
Anda mungkin tidak akan menyadarinya.
>> Lain kompleksitas asimtotik adalah,
waktu logaritmik, O (log n).
Sebuah contoh dari suatu algoritma yang berjalan cepat ini
adalah algoritma biner klasik pencarian,
untuk menemukan elemen dalam daftar yang sudah diurutkan elemen.
>> Jika Anda tidak tahu apa pencarian biner tidak,
Saya akan menjelaskannya untuk Anda benar-benar cepat.
Katakanlah Anda sedang mencari nomor 3
dalam array bilangan bulat.
Ini terlihat pada elemen tengah dari array
dan bertanya, "Apakah unsur saya ingin lebih besar dari, sama dengan, atau kurang dari ini?"
Jika itu sama, maka besar. Anda menemukan elemen, dan Anda sudah selesai.
Jika itu lebih besar, maka Anda tahu elemen
harus berada di sisi kanan dari array,
dan Anda hanya bisa melihat bahwa di masa depan,
dan jika lebih kecil, maka Anda tahu itu harus berada di sisi kiri.
Proses ini kemudian diulang dengan array yang lebih kecil ukuran
sampai elemen yang benar ditemukan.
>> Ini algoritma yang kuat memotong ukuran array dalam setengah dengan setiap operasi.
Jadi, untuk menemukan elemen dalam array diurutkan dari ukuran 8,
paling (log ₂ 8),
atau 3 dari operasi ini,
memeriksa elemen tengah, kemudian memotong array di setengah akan diperlukan,
sedangkan array ukuran 16 mengambil (log ₂ 16),
atau 4 operasi.
Itu hanya 1 operasi lebih untuk array dua kali lipat ukuran.
Menggandakan ukuran array
meningkatkan runtime dengan hanya 1 sepotong kode ini.
Sekali lagi, memeriksa elemen tengah daftar, kemudian membelah.
Jadi, itu dikatakan beroperasi dalam waktu logaritmik,
O (log n).
Tapi tunggu, Anda katakan,
tidak ini tergantung pada di mana dalam daftar elemen yang Anda cari adalah?
Bagaimana jika elemen pertama Anda melihat kebetulan yang benar?
Kemudian, hanya membutuhkan waktu 1 operasi,
tidak peduli seberapa besar daftar ini.
>> Nah, itu sebabnya ilmuwan komputer memiliki istilah yang lebih
untuk kompleksitas asimtotik yang mencerminkan kasus terbaik
dan kasus terburuk kinerja dari algoritma.
Lebih baik, atas dan batas bawah
pada runtime.
Dalam kasus terbaik untuk pencarian biner, elemen kita
tepat di tengah,
dan Anda mendapatkannya dalam waktu yang konstan,
tidak peduli seberapa besar sisa array.
Simbol yang digunakan untuk ini adalah Ω.
Jadi, algoritma ini dikatakan berjalan dalam Ω (1).
Dalam kasus terbaik, ia menemukan unsur dengan cepat,
tidak peduli seberapa besar array adalah,
namun dalam kasus terburuk,
itu harus melakukan (log n) cek perpecahan
dari array untuk menemukan elemen yang tepat.
Terburuk batas-huruf besar yang disebut dengan big "O" yang Anda sudah tahu.
Jadi, itu O (log n), namun Ω (1).
>> Sebuah pencarian linier, sebaliknya,
di mana Anda berjalan melalui setiap elemen dari array
untuk menemukan yang Anda inginkan,
adalah pada Ω terbaik (1).
Sekali lagi, elemen pertama Anda inginkan.
Jadi, tidak peduli seberapa besar array.
Dalam kasus terburuk, itu adalah elemen terakhir dalam array.
Jadi, Anda harus berjalan melalui semua elemen n dalam array untuk menemukan itu,
seperti jika Anda sedang mencari 3 a.
Jadi, itu berjalan dalam O (n) waktu
karena itu sebanding dengan jumlah elemen dalam array.
>> Satu simbol yang lebih digunakan adalah Θ.
Hal ini dapat digunakan untuk menggambarkan algoritma di mana kasus-kasus terbaik dan terburuk
adalah sama.
Ini adalah kasus dalam string-panjang algoritma kita bicarakan sebelumnya.
Artinya, jika kita menyimpannya dalam variabel sebelum
kita menyimpan string dan mengaksesnya kemudian dalam waktu yang konstan.
Tidak peduli apa nomor
kita menyimpan dalam variabel itu, kita harus melihatnya.
Kasus terbaik adalah, kita melihat hal itu
dan menemukan panjang string.
Jadi Ω (1) atau terbaik-kasus waktu konstan.
Kasus terburuk adalah,
kita melihat dan menemukan panjang string.
Jadi, O (1) atau waktu konstan dalam kasus terburuk.
Jadi, sejak kasus terbaik dan kasus terburuk adalah sama,
ini dapat dikatakan berjalan dalam Θ (1) waktu.
>> Singkatnya, kita memiliki cara yang baik untuk alasan tentang efisiensi kode
tanpa mengetahui apa-apa tentang waktu dunia nyata mereka diperlukan untuk menjalankan,
yang dipengaruhi oleh banyak faktor luar,
termasuk hardware yang berbeda, perangkat lunak,
atau spesifik dari kode Anda.
Juga, memungkinkan kita untuk berfikir dengan baik tentang apa yang akan terjadi
ketika ukuran dari kenaikan input.
>> Jika Anda berjalan di algoritma O (n) ²,
atau lebih buruk lagi, O (2 ⁿ) algoritma,
salah satu jenis yang paling cepat berkembang,
Anda benar-benar akan mulai melihat perlambatan
ketika Anda mulai bekerja dengan sejumlah besar data.
>> Itu kompleksitas asimtotik. Terima kasih.