[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.