Kebanyakan orang dengan gelar di CS pasti akan tahu apa yang Big O adalah singkatan . Ini membantu kita untuk mengukur seberapa baik suatu skala algoritma.
Tapi saya ingin tahu, bagaimana Anda menghitung atau memperkirakan kompleksitas algoritma Anda?
Jawaban:
Saya akan melakukan yang terbaik untuk menjelaskannya di sini dengan persyaratan yang sederhana, tetapi diingatkan bahwa topik ini membutuhkan siswa saya beberapa bulan untuk akhirnya memahami. Anda dapat menemukan informasi lebih lanjut tentang Bab 2 Struktur Data dan Algoritma di buku Java .
Tidak ada prosedur mekanis yang dapat digunakan untuk mendapatkan BigOh.
Sebagai "buku masak", untuk mendapatkan BigOh dari sepotong kode, pertama-tama Anda harus menyadari bahwa Anda sedang membuat rumus matematika untuk menghitung berapa banyak langkah perhitungan yang dijalankan dengan input ukuran tertentu.
Tujuannya sederhana: untuk membandingkan algoritma dari sudut pandang teoretis, tanpa perlu mengeksekusi kode. Semakin sedikit jumlah langkah, semakin cepat algoritma.
Misalnya, katakan Anda memiliki kode ini:
Fungsi ini mengembalikan jumlah semua elemen array, dan kami ingin membuat rumus untuk menghitung kompleksitas komputasi dari fungsi itu:
Jadi kita punya
f(N)
, fungsi untuk menghitung jumlah langkah komputasi. Input dari fungsi adalah ukuran struktur untuk diproses. Ini berarti bahwa fungsi ini disebut seperti:Parameter
N
mengambildata.length
nilainya. Sekarang kita membutuhkan definisi fungsi yang sebenarnyaf()
. Ini dilakukan dari kode sumber, di mana setiap baris yang menarik diberi nomor dari 1 hingga 4.Ada banyak cara untuk menghitung BigOh. Dari titik ini ke depan kita akan mengasumsikan bahwa setiap kalimat yang tidak tergantung pada ukuran data input mengambil konstanta
C
langkah perhitungan angka .Kita akan menambahkan jumlah individu dari langkah-langkah fungsi, dan deklarasi variabel lokal atau pernyataan pengembalian tidak tergantung pada ukuran
data
array.Itu berarti bahwa baris 1 dan 4 masing-masing mengambil jumlah langkah C, dan fungsinya agak seperti ini:
Bagian selanjutnya adalah mendefinisikan nilai
for
pernyataan. Ingat bahwa kami menghitung jumlah langkah komputasi, yang berarti bahwa tubuhfor
pernyataan dieksekusiN
kali. Itu sama dengan menambahkanC
,N
kali:Tidak ada aturan mekanis untuk menghitung berapa kali tubuh
for
dieksekusi, Anda perlu menghitungnya dengan melihat apa yang dilakukan kode. Untuk menyederhanakan perhitungan, kami mengabaikan inisialisasi variabel, kondisi dan bagian kenaikan darifor
pernyataan.Untuk mendapatkan BigOh yang sebenarnya, kita perlu analisis fungsi asimptotik . Ini kira-kira dilakukan seperti ini:
C
.f()
dapatkan polinomium di dalamnyastandard form
.N
mendekatiinfinity
.Kami
f()
memiliki dua istilah:Mengambil semua
C
konstanta dan bagian yang berlebihan:Karena istilah terakhir adalah yang tumbuh lebih besar ketika
f()
mendekati tak terhingga (pikirkan batas ) ini adalah argumen BigOh, dansum()
fungsinya memiliki BigOh dari:Ada beberapa trik untuk menyelesaikan beberapa trik rumit: gunakan penjumlahan kapan saja Anda bisa.
Sebagai contoh, kode ini dapat dipecahkan dengan mudah menggunakan penjumlahan:
Hal pertama yang perlu Anda tanyakan adalah urutan eksekusi
foo()
. Sementara yang biasa terjadiO(1)
, Anda perlu bertanya kepada profesor Anda tentang hal itu.O(1)
berarti (hampir, sebagian besar) konstanC
, tidak tergantung ukuranN
.The
for
pernyataan di satu nomor kalimat rumit. Sementara indeks berakhir pada2 * N
, kenaikan dilakukan oleh dua. Itu berarti bahwa langkah pertamafor
hanya dijalankanN
, dan kita perlu membagi hitungannya menjadi dua.Kalimat nomor dua bahkan lebih rumit karena tergantung pada nilai
i
. Lihatlah: indeks i mengambil nilai-nilai: 0, 2, 4, 6, 8, ..., 2 * N, dan yang keduafor
dijalankan: N kali yang pertama, N - 2 yang kedua, N - 4 yang ketiga ... sampai ke tahap N / 2, di mana yang keduafor
tidak pernah dieksekusi.Pada formula, itu berarti:
Sekali lagi, kami menghitung jumlah langkah . Dan menurut definisi, setiap penjumlahan harus selalu dimulai dari satu, dan diakhiri dengan angka yang lebih besar atau sama dengan satu.
(Kami menganggap itu
foo()
adalahO(1)
dan mengambilC
langkah-langkah.)Kami memiliki masalah di sini: ketika
i
mengambil nilaiN / 2 + 1
ke atas, Penjumlahan batin berakhir pada angka negatif! Itu tidak mungkin dan salah. Kita perlu membagi penjumlahan menjadi dua, menjadi titik penting saati
dibutuhkanN / 2 + 1
.Sejak momen penting
i > N / 2
, batinfor
tidak akan dieksekusi, dan kami mengasumsikan kompleksitas eksekusi C konstan pada tubuhnya.Sekarang penjumlahan dapat disederhanakan menggunakan beberapa aturan identitas:
w
)Menerapkan beberapa aljabar:
Dan BigOh adalah:
sumber
O(n)
sinilahn
jumlah elemen, atau diO(x*y)
manax
dany
merupakan dimensi array. Besar-oh adalah "relatif terhadap input", jadi itu tergantung pada apa input Anda.Big O memberikan batas atas untuk kompleksitas waktu suatu algoritma. Ini biasanya digunakan bersamaan dengan pemrosesan set data (daftar) tetapi dapat digunakan di tempat lain.
Beberapa contoh bagaimana ini digunakan dalam kode C.
Katakanlah kita memiliki array n elemen
Jika kita ingin mengakses elemen pertama array, ini akan menjadi O (1) karena tidak peduli seberapa besar array, selalu dibutuhkan waktu konstan yang sama untuk mendapatkan item pertama.
Jika kami ingin menemukan nomor dalam daftar:
Ini akan menjadi O (n) karena paling banyak kita harus melihat seluruh daftar untuk menemukan nomor kita. Big-O masih O (n) meskipun kita mungkin menemukan nomor kita yang pertama kali coba dan jalankan melalui loop sekali karena Big-O menggambarkan batas atas untuk suatu algoritma (omega untuk batas bawah dan theta untuk batas ketat) .
Ketika kita mendapatkan loop bersarang:
Ini adalah O (n ^ 2) karena untuk setiap lintasan loop luar (O (n)) kita harus melalui seluruh daftar lagi sehingga n melipatgandakan kita dengan n kuadrat.
Ini nyaris tidak menggores permukaan tetapi ketika Anda bisa menganalisis algoritma yang lebih kompleks matematika kompleks yang melibatkan bukti ikut bermain. Semoga ini membiasakan Anda dengan dasar-dasar setidaknya.
sumber
O(1)
bekerja sendiri. Dalam C API standar misalnya,bsearch
secara inherenO(log n)
,strlen
adalahO(n)
, danqsort
merupakanO(n log n)
(secara teknis tidak memiliki jaminan, dan quicksort sendiri memiliki kompleksitas kasus terburuk dariO(n²)
, tetapi dengan asumsi Andalibc
penulis tidak tolol, kompleksitas kasus rata-rata adalahO(n log n)
dan menggunakan strategi pemilihan pivot yang mengurangi kemungkinan memukulO(n²)
kasus). Dan keduanyabsearch
danqsort
bisa lebih buruk jika fungsi komparator bersifat patologis.Meskipun mengetahui cara mengetahui waktu O Besar untuk masalah khusus Anda bermanfaat, mengetahui beberapa kasus umum dapat membantu Anda membuat keputusan dalam algoritme Anda.
Berikut adalah beberapa kasus yang paling umum, diangkat dari http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :
O (1) - Menentukan apakah suatu bilangan genap atau ganjil; menggunakan tabel pencarian ukuran konstan atau tabel hash
O (logn) - Menemukan item dalam array yang diurutkan dengan pencarian biner
O (n) - Menemukan item dalam daftar yang tidak disortir; menambahkan dua angka n-digit
O (n 2 ) - Mengalikan dua angka n-digit dengan algoritma sederhana; menambahkan dua n × n matriks; semacam gelembung atau jenis sisipan
O (n 3 ) - Mengalikan dua n × n matriks dengan algoritma sederhana
O (c n ) - Menemukan solusi (tepat) untuk masalah salesman keliling menggunakan pemrograman dinamis; menentukan apakah dua pernyataan logis setara dengan menggunakan brute force
O (n!) - Memecahkan masalah salesman keliling melalui pencarian brute-force
Di n ) - Sering digunakan alih-alih O (n!) Untuk mendapatkan formula yang lebih sederhana untuk kompleksitas asimptotik
sumber
x&1==1
untuk memeriksa keanehan?x & 1
sudah cukup, tidak perlu memeriksa== 1
; di C,x&1==1
dievaluasi sebagaix&(1==1)
berkat prioritas operator , jadi sebenarnya sama dengan pengujianx&1
). Saya pikir Anda salah membaca jawabannya; ada titik koma di sana, bukan koma. Itu tidak mengatakan Anda akan membutuhkan tabel pencarian untuk pengujian genap / ganjil, itu mengatakan baik pengujian genap / ganjil dan memeriksa tabel pencarian adalahO(1)
operasi.Pengingat kecil:
big O
notasi digunakan untuk menunjukkan kompleksitas asimptotik (yaitu, ketika ukuran masalah tumbuh hingga tak terbatas), dan menyembunyikan konstanta.Ini berarti bahwa antara suatu algoritma dalam O (n) dan satu dalam O (n 2 ), yang tercepat tidak selalu yang pertama (meskipun selalu ada nilai n sehingga untuk masalah ukuran> n, algoritma pertama adalah Tercepat).
Perhatikan bahwa konstanta tersembunyi sangat tergantung pada implementasinya!
Juga, dalam beberapa kasus, runtime bukan fungsi deterministik dari ukuran n input. Ambil pengurutan menggunakan pengurutan cepat misalnya: waktu yang diperlukan untuk mengurutkan array dari elemen n tidak konstan tetapi tergantung pada konfigurasi awal array.
Ada kompleksitas waktu yang berbeda:
Kasus rata-rata (biasanya jauh lebih sulit untuk diketahui ...)
...
Pengantar yang baik adalah Pengantar Analisis Algoritma oleh R. Sedgewick dan P. Flajolet.
Seperti yang Anda katakan,,
premature optimisation is the root of all evil
dan (jika mungkin) pembuatan profil harus selalu digunakan ketika mengoptimalkan kode. Bahkan dapat membantu Anda menentukan kompleksitas algoritma Anda.sumber
Melihat jawabannya di sini saya pikir kita dapat menyimpulkan bahwa sebagian besar dari kita memang mendekati urutan algoritma dengan melihatnya dan menggunakan akal sehat alih-alih menghitungnya dengan, misalnya, metode master seperti yang kita pikirkan di universitas. Dengan mengatakan itu saya harus menambahkan bahwa bahkan profesor mendorong kita (kemudian) untuk benar-benar memikirkannya , bukan hanya menghitungnya.
Saya juga ingin menambahkan bagaimana hal itu dilakukan untuk fungsi rekursif :
misalkan kita memiliki fungsi seperti ( kode skema ):
yang secara rekursif menghitung faktorial dari angka yang diberikan.
Langkah pertama adalah mencoba dan menentukan karakteristik kinerja untuk tubuh fungsi saja dalam hal ini, tidak ada yang istimewa yang dilakukan dalam tubuh, hanya perkalian (atau kembalinya nilai 1).
Jadi kinerja untuk tubuh adalah: O (1) (konstan).
Selanjutnya coba dan tentukan ini untuk jumlah panggilan rekursif . Dalam hal ini kami memiliki panggilan rekursif n-1.
Jadi kinerja untuk panggilan rekursif adalah: O (n-1) (urutan n, karena kami membuang bagian-bagian yang tidak penting).
Kemudian satukan keduanya dan Anda kemudian memiliki kinerja untuk seluruh fungsi rekursif:
1 * (n-1) = O (n)
Peter , untuk menjawab masalah Anda yang diangkat; metode yang saya jelaskan di sini sebenarnya menangani ini dengan cukup baik. Tetapi perlu diingat bahwa ini masih merupakan perkiraan dan bukan jawaban yang benar secara matematis sepenuhnya. Metode yang dijelaskan di sini juga merupakan salah satu metode yang kami ajarkan di universitas, dan jika saya ingat dengan benar digunakan untuk algoritma yang jauh lebih maju daripada faktorial yang saya gunakan dalam contoh ini.
Tentu saja itu semua tergantung pada seberapa baik Anda dapat memperkirakan waktu berjalan dari fungsi dan jumlah panggilan rekursif, tetapi itu juga berlaku untuk metode lainnya.
sumber
Jika biaya Anda adalah polinomial, simpan saja istilah urutan tertinggi, tanpa pengali. Misalnya:
Ini tidak bekerja untuk seri tak terbatas, ingatlah. Tidak ada resep tunggal untuk kasus umum, meskipun untuk beberapa kasus umum, ketidaksetaraan berikut berlaku:
sumber
Saya memikirkannya dalam hal informasi. Setiap masalah terdiri dari mempelajari sejumlah bit.
Alat dasar Anda adalah konsep poin keputusan dan entropinya. Entropi poin keputusan adalah informasi rata-rata yang akan diberikannya kepada Anda. Misalnya, jika suatu program berisi titik keputusan dengan dua cabang, entropinya adalah jumlah dari probabilitas setiap cabang dikali log 2 dari probabilitas terbalik dari cabang itu. Itulah cara Anda belajar dengan menjalankan keputusan itu.
Misalnya,
if
pernyataan yang memiliki dua cabang, keduanya memiliki kemungkinan yang sama, memiliki entropi 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Jadi entropinya adalah 1 bit.Misalkan Anda mencari tabel item N, seperti N = 1024. Itu adalah masalah 10-bit karena log (1024) = 10 bit. Jadi, jika Anda dapat mencarinya dengan pernyataan IF yang memiliki hasil yang sama-sama memungkinkan, harus diambil 10 keputusan.
Itu yang Anda dapatkan dengan pencarian biner.
Misalkan Anda melakukan pencarian linier. Anda melihat elemen pertama dan bertanya apakah itu yang Anda inginkan. Probabilitasnya 1/1024, dan 1023/1024 tidak. Entropi dari keputusan itu adalah 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * sekitar 0 = sekitar 0,01 bit. Anda telah belajar sangat sedikit! Keputusan kedua tidak jauh lebih baik. Itu sebabnya pencarian linier sangat lambat. Bahkan itu eksponensial dalam jumlah bit yang perlu Anda pelajari.
Misalkan Anda melakukan pengindeksan. Misalkan tabel sudah disortir menjadi banyak tempat sampah, dan Anda menggunakan beberapa bit di kunci untuk mengindeks langsung ke entri tabel. Jika ada 1024 nampan, entropinya adalah 1/1024 * log (1024) + 1/1024 * log (1024) + ... untuk semua kemungkinan hasil 1024. Ini adalah 1/1024 * 10 kali 1024 hasil, atau 10 bit entropi untuk operasi pengindeksan satu itu. Itu sebabnya pencarian pengindeksan cepat.
Sekarang pikirkan tentang penyortiran. Anda memiliki N item, dan Anda memiliki daftar. Untuk setiap item, Anda harus mencari ke mana item itu masuk dalam daftar, dan kemudian menambahkannya ke daftar. Jadi pengurutan membutuhkan sekitar N kali jumlah langkah pencarian yang mendasarinya.
Jadi macam berdasarkan keputusan biner memiliki hasil yang kira-kira sama kemungkinannya mengambil langkah O (N log N). Algoritma pengurutan O (N) dimungkinkan jika didasarkan pada pencarian pengindeksan.
Saya telah menemukan bahwa hampir semua masalah kinerja algoritmik dapat dilihat dengan cara ini.
sumber
Mari kita mulai dari awal.
Pertama-tama, terima prinsip bahwa operasi sederhana tertentu pada data dapat dilakukan dalam
O(1)
waktu, yaitu, dalam waktu yang tidak tergantung pada ukuran input. Operasi primitif dalam C ini terdiri dariPembenaran untuk prinsip ini membutuhkan studi rinci tentang instruksi mesin (langkah primitif) dari komputer biasa. Setiap operasi yang dijelaskan dapat dilakukan dengan sejumlah kecil instruksi mesin; seringkali hanya satu atau dua instruksi yang diperlukan. Sebagai konsekuensinya, beberapa jenis pernyataan dalam C dapat dieksekusi dalam
O(1)
waktu, yaitu, dalam jumlah waktu yang konstan tanpa tergantung input. Ini termasuk sederhanaDalam C, banyak for-loop dibentuk dengan menginisialisasi variabel indeks ke beberapa nilai dan menambah variabel dengan 1 setiap kali di sekitar loop. For-loop berakhir ketika indeks mencapai batas tertentu. Misalnya, untuk-loop
menggunakan variabel indeks i. Itu bertambah 1 kali setiap loop, dan iterasi berhenti ketika saya mencapai n - 1.
Namun, untuk saat ini, fokus pada bentuk sederhana untuk-loop, di mana perbedaan antara nilai-nilai akhir dan awal, dibagi dengan jumlah di mana variabel indeks bertambah memberitahu kita berapa kali kita berkeliling loop . Hitungan itu tepat, kecuali ada cara untuk keluar dari loop melalui pernyataan lompat; itu adalah batas atas jumlah iterasi dalam hal apa pun.
Misalnya, untuk loop berulang
((n − 1) − 0)/1 = n − 1 times
, karena 0 adalah nilai awal dari i, n - 1 adalah nilai tertinggi yang dicapai oleh i (yaitu, ketika saya mencapai n − 1, loop berhenti dan tidak ada iterasi yang terjadi dengan i = n− 1), dan 1 ditambahkan ke i pada setiap iterasi dari loop.Dalam kasus paling sederhana, di mana waktu yang dihabiskan dalam tubuh loop adalah sama untuk setiap iterasi, kita dapat mengalikan batas atas-oh besar untuk tubuh dengan jumlah kali di sekitar loop . Sebenarnya, kita harus menambahkan O (1) waktu untuk menginisialisasi indeks loop dan O (1) waktu untuk perbandingan pertama dari indeks loop dengan batas , karena kita menguji sekali lagi daripada kita memutari loop. Namun, kecuali dimungkinkan untuk menjalankan loop nol kali, waktu untuk menginisialisasi loop dan menguji batas sekali adalah istilah tingkat rendah yang dapat dijatuhkan oleh aturan penjumlahan.
Sekarang perhatikan contoh ini:
Kita tahu bahwa baris (1) membutuhkan
O(1)
waktu. Jelas, kita berputar di sekitar loop n kali, karena kita dapat menentukan dengan mengurangi batas bawah dari batas atas yang ditemukan pada baris (1) dan kemudian menambahkan 1. Karena tubuh, baris (2), membutuhkan O (1) waktu, kita dapat mengabaikan waktu untuk meningkatkan j dan waktu untuk membandingkan j dengan n, yang keduanya juga O (1). Jadi, waktu berjalan dari baris (1) dan (2) adalah produk dari n dan O (1) , yaituO(n)
.Demikian pula, kita dapat mengikat waktu berjalan dari loop luar yang terdiri dari garis (2) hingga (4), yaitu
Kami telah menetapkan bahwa loop baris (3) dan (4) membutuhkan waktu O (n). Dengan demikian, kita dapat mengabaikan O (1) waktu untuk meningkatkan i dan untuk menguji apakah i <n dalam setiap iterasi, menyimpulkan bahwa setiap iterasi dari loop luar membutuhkan O (n) waktu.
Inisialisasi i = 0 dari loop luar dan (n +1) tes kondisi i <n juga mengambil O (1) waktu dan dapat diabaikan. Akhirnya, kami mengamati bahwa kami berkeliling loop luar n kali, mengambil O (n) waktu untuk setiap iterasi, memberikan total
O(n^2)
waktu berjalan.Contoh yang lebih praktis.
sumber
Jika Anda ingin memperkirakan urutan kode Anda secara empiris alih-alih dengan menganalisis kode, Anda dapat menempel pada serangkaian peningkatan nilai n dan waktu kode Anda. Plot timing Anda pada skala log. Jika kodenya O (x ^ n), nilainya harus jatuh pada garis kemiringan n.
Ini memiliki beberapa keunggulan dibandingkan hanya mempelajari kode. Untuk satu hal, Anda dapat melihat apakah Anda berada dalam kisaran di mana run time mendekati urutan asimptotiknya. Juga, Anda mungkin menemukan bahwa beberapa kode yang Anda pikir adalah pesanan O (x) benar-benar pesanan O (x ^ 2), misalnya, karena waktu yang dihabiskan untuk panggilan perpustakaan.
sumber
Pada dasarnya hal yang muncul hingga 90% dari waktu hanyalah menganalisis loop. Apakah Anda memiliki loop bersarang tunggal, ganda, tiga? Anda memiliki O (n), O (n ^ 2), O (n ^ 3) waktu berjalan.
Sangat jarang (kecuali jika Anda menulis platform dengan pustaka basis yang luas (seperti misalnya .NET BCL, atau C ++ 's STL), Anda akan menemukan apa pun yang lebih sulit daripada hanya melihat loop Anda (untuk pernyataan, sementara, goto, dll ...)
sumber
Notasi O besar berguna karena mudah digunakan dan menyembunyikan komplikasi dan detail yang tidak perlu (untuk beberapa definisi yang tidak perlu). Salah satu cara yang bagus untuk mengetahui kompleksitas algoritma divide and conquer adalah metode tree. Katakanlah Anda memiliki versi quicksort dengan prosedur median, jadi Anda membagi array menjadi sub-array yang seimbang sempurna setiap saat.
Sekarang bangun pohon yang sesuai dengan semua array yang bekerja dengan Anda. Pada root Anda memiliki larik asli, root memiliki dua anak yang merupakan subarrays. Ulangi ini sampai Anda memiliki array elemen tunggal di bagian bawah.
Karena kita dapat menemukan median dalam waktu O (n) dan membagi array menjadi dua bagian dalam waktu O (n), pekerjaan yang dilakukan pada setiap node adalah O (k) di mana k adalah ukuran array. Setiap level dari pohon berisi (paling banyak) seluruh array sehingga pekerjaan per level adalah O (n) (ukuran dari subarrays ditambahkan hingga n, dan karena kami memiliki O (k) per level kami dapat menambahkan ini) . Hanya ada level log (n) di pohon karena setiap kali kita membagi dua input.
Oleh karena itu kita dapat membatasi jumlah pekerjaan dengan O (n * log (n)).
Namun, Big O menyembunyikan beberapa detail yang terkadang tidak bisa kita abaikan. Pertimbangkan menghitung urutan Fibonacci dengan
dan mari kita asumsikan a dan b adalah BigIntegers di Java atau sesuatu yang dapat menangani angka besar secara sewenang-wenang. Kebanyakan orang akan mengatakan ini adalah algoritma O (n) tanpa gentar. Alasannya adalah bahwa Anda memiliki n iterasi dalam for loop dan O (1) bekerja di samping loop.
Tetapi bilangan Fibonacci besar, bilangan Fibonacci ke-n adalah eksponensial dalam n jadi hanya menyimpannya akan mengambil urutan n byte. Performa tambahan dengan bilangan bulat besar akan membutuhkan O (n) jumlah pekerjaan. Jadi jumlah total pekerjaan yang dilakukan dalam prosedur ini adalah
1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)
Jadi algoritma ini berjalan dalam waktu kuadrat!
sumber
Kurang berguna secara umum, saya pikir, tetapi demi kelengkapan ada juga Big Omega Ω , yang mendefinisikan batas bawah pada kompleksitas algoritma, dan Big Theta Θ , yang mendefinisikan batas atas dan bawah.
sumber
Hancurkan algoritma menjadi beberapa bagian yang Anda ketahui notasi O besar, dan gabungkan melalui operator O besar. Itulah satu-satunya cara yang saya tahu.
Untuk informasi lebih lanjut, periksa halaman Wikipedia tentang masalah ini.
sumber
Keakraban dengan algoritma / struktur data yang saya gunakan dan / atau analisis sekilas iterasi bersarang. Kesulitannya adalah ketika Anda memanggil fungsi pustaka, mungkin beberapa kali - Anda sering tidak yakin apakah Anda memanggil fungsi tersebut secara tidak perlu pada waktu atau implementasi apa yang mereka gunakan. Mungkin fungsi perpustakaan harus memiliki ukuran kompleksitas / efisiensi, apakah itu Big O atau metrik lain, yang tersedia dalam dokumentasi atau bahkan IntelliSense .
sumber
Adapun "bagaimana Anda menghitung" Big O, ini adalah bagian dari teori kompleksitas Komputasi . Untuk beberapa (banyak) kasus khusus Anda mungkin dapat datang dengan beberapa heuristik sederhana (seperti mengalikan jumlah loop untuk loop bersarang), esp. ketika semua yang Anda inginkan adalah estimasi batas atas, dan Anda tidak keberatan jika terlalu pesimis - yang saya kira mungkin adalah pertanyaan Anda.
Jika Anda benar-benar ingin menjawab pertanyaan Anda untuk algoritma apa pun, yang terbaik yang dapat Anda lakukan adalah menerapkan teori tersebut. Selain analisis "kasus terburuk" yang sederhana, saya merasa analisis Amortisasi sangat berguna dalam praktiknya.
sumber
Untuk kasus 1, loop dalam dieksekusi
n-i
kali, jadi jumlah total eksekusi adalah jumlah untuki
pergi dari0
ken-1
(karena lebih rendah dari, tidak lebih rendah dari atau sama) darin-i
. Anda akhirnyan*(n + 1) / 2
, jadiO(n²/2) = O(n²)
.Untuk loop ke-2,
i
berada di antara0
dann
termasuk untuk loop luar; maka loop dalam dieksekusi ketikaj
benar-benar lebih besar darin
, yang kemudian mustahil.sumber
Selain menggunakan metode master (atau salah satu spesialisasinya), saya menguji algoritme saya secara eksperimental. Ini tidak dapat membuktikan bahwa setiap kelas kompleksitas tertentu tercapai, tetapi dapat memberikan jaminan bahwa analisis matematika sesuai. Untuk membantu dengan jaminan ini, saya menggunakan alat cakupan kode bersama dengan eksperimen saya, untuk memastikan bahwa saya menggunakan semua kasing.
Sebagai contoh yang sangat sederhana katakan Anda ingin melakukan pemeriksaan kewarasan pada kecepatan semacam daftar .NET framework. Anda bisa menulis sesuatu seperti berikut ini, kemudian menganalisis hasilnya di Excel untuk memastikan mereka tidak melebihi kurva n * log (n).
Dalam contoh ini saya mengukur jumlah perbandingan, tetapi juga bijaksana untuk memeriksa waktu aktual yang diperlukan untuk setiap ukuran sampel. Namun kemudian Anda harus lebih berhati-hati bahwa Anda hanya mengukur algoritma dan tidak termasuk artefak dari infrastruktur pengujian Anda.
sumber
Jangan lupa untuk memungkinkan kompleksitas ruang yang juga dapat menjadi penyebab kekhawatiran jika seseorang memiliki sumber daya memori yang terbatas. Jadi misalnya Anda mungkin mendengar seseorang menginginkan algoritma ruang konstan yang pada dasarnya merupakan cara untuk mengatakan bahwa jumlah ruang yang diambil oleh algoritma tidak tergantung pada faktor apa pun di dalam kode.
Kadang-kadang kompleksitas dapat datang dari berapa kali sesuatu dipanggil, seberapa sering loop dieksekusi, seberapa sering memori dialokasikan, dan sebagainya adalah bagian lain untuk menjawab pertanyaan ini.
Terakhir, O besar dapat digunakan untuk kasus terburuk, kasus terbaik, dan kasus amortisasi di mana umumnya itu adalah kasus terburuk yang digunakan untuk menggambarkan seberapa buruk suatu algoritma.
sumber
Yang sering diabaikan adalah perilaku yang diharapkan dari algoritma Anda. Itu tidak mengubah Big-O dari algoritme Anda , tetapi itu berhubungan dengan pernyataan "optimasi prematur ..."
Perilaku yang diharapkan dari algoritma Anda adalah - sangat tercengang - seberapa cepat Anda dapat mengharapkan algoritma Anda bekerja pada data yang paling mungkin Anda lihat.
Misalnya, jika Anda mencari nilai dalam daftar, itu O (n), tetapi jika Anda tahu bahwa sebagian besar daftar yang Anda lihat memiliki nilai Anda di depan, perilaku khas algoritma Anda lebih cepat.
Untuk benar-benar memahaminya, Anda harus dapat menggambarkan distribusi probabilitas "ruang input" Anda (jika Anda perlu mengurutkan daftar, seberapa sering daftar itu akan disortir? Seberapa sering itu terbalik total? Bagaimana sering itu sebagian besar diurutkan?) Tidak selalu layak bahwa Anda tahu itu, tetapi terkadang Anda melakukannya.
sumber
pertanyaan bagus!
Penafian: jawaban ini berisi pernyataan salah lihat komentar di bawah.
Jika Anda menggunakan Big O, Anda berbicara tentang kasus terburuk (lebih lanjut tentang apa artinya nanti). Selain itu, ada modal theta untuk kasus rata-rata dan omega besar untuk kasus terbaik.
Lihatlah situs ini untuk mendapatkan definisi resmi tentang Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html
Oke, jadi sekarang apa yang kita maksud dengan kompleksitas "kasus terbaik" dan "kasus terburuk"?
Ini mungkin digambarkan paling jelas melalui contoh. Sebagai contoh jika kita menggunakan pencarian linear untuk menemukan angka dalam array yang diurutkan maka kasus terburuk adalah ketika kita memutuskan untuk mencari elemen terakhir dari array karena ini akan mengambil langkah sebanyak yang ada item dalam array. Kasus terbaik adalah ketika kita mencari elemen pertama karena kita akan selesai setelah pemeriksaan pertama.
Inti dari semua kompleksitas kata sifat ini adalah bahwa kami sedang mencari cara untuk membuat grafik jumlah waktu yang dihabiskan oleh program hipotetis dalam hal ukuran variabel tertentu. Namun untuk banyak algoritma, Anda dapat berargumen bahwa tidak ada waktu untuk ukuran input tertentu. Perhatikan bahwa ini bertentangan dengan persyaratan mendasar dari suatu fungsi, input apa pun harus memiliki tidak lebih dari satu output. Jadi kami datang dengan beberapa fungsi untuk menggambarkan kompleksitas suatu algoritma. Sekarang, walaupun mencari sebuah array ukuran n mungkin membutuhkan jumlah waktu yang bervariasi tergantung pada apa yang Anda cari dalam array dan bergantung secara proporsional ke n, kami dapat membuat deskripsi informatif dari algoritma menggunakan kasus terbaik, kasus rata-rata , dan kelas kasus terburuk.
Maaf ini ditulis dengan buruk dan tidak memiliki banyak informasi teknis. Tapi mudah-mudahan ini akan membuat kelas kompleksitas waktu lebih mudah untuk dipikirkan. Setelah Anda merasa nyaman dengan ini, itu menjadi masalah sederhana penguraian melalui program Anda dan mencari hal-hal seperti untuk-loop yang tergantung pada ukuran array dan penalaran berdasarkan pada struktur data Anda input apa yang akan menghasilkan kasus-kasus sepele dan input apa yang akan dihasilkan dalam kasus terburuk.
sumber
Saya tidak tahu bagaimana menyelesaikan ini secara terprogram, tetapi hal pertama yang dilakukan orang adalah bahwa kami mencicipi algoritma untuk pola tertentu dalam jumlah operasi yang dilakukan, katakanlah 4n ^ 2 + 2n + 1 kami memiliki 2 aturan:
Jika kita menyederhanakan f (x), di mana f (x) adalah rumus untuk jumlah operasi yang dilakukan, (4n ^ 2 + 2n + 1 dijelaskan di atas), kita memperoleh nilai O-besar [O (n ^ 2) dalam hal ini kasus]. Tetapi ini harus memperhitungkan interpolasi Lagrange dalam program, yang mungkin sulit untuk diterapkan. Dan bagaimana jika nilai big-O nyata adalah O (2 ^ n), dan kita mungkin memiliki sesuatu seperti O (x ^ n), jadi algoritma ini mungkin tidak akan diprogram. Tetapi jika seseorang membuktikan saya salah, berikan saya kodenya. . . .
sumber
Untuk kode A, loop luar akan dieksekusi untuk
n+1
kali, waktu '1' berarti proses yang memeriksa apakah saya masih memenuhi persyaratan. Dan loop dalam berjalann
kali,n-2
kali .... Jadi0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)
,.Untuk kode B, meskipun loop dalam tidak akan masuk dan menjalankan foo (), loop dalam akan dieksekusi untuk n kali tergantung pada waktu eksekusi loop luar, yaitu O (n)
sumber
Saya ingin menjelaskan Big-O dalam aspek yang sedikit berbeda.
Big-O hanya untuk membandingkan kerumitan program yang berarti seberapa cepat mereka tumbuh ketika input meningkat dan bukan waktu yang tepat yang dihabiskan untuk melakukan tindakan.
IMHO dalam rumus-O besar Anda lebih baik tidak menggunakan persamaan yang lebih kompleks (Anda mungkin hanya berpegang pada yang ada dalam grafik berikut.) Namun Anda masih dapat menggunakan rumus lain yang lebih tepat (seperti 3 ^ n, n ^ 3, .. .) tetapi lebih dari itu terkadang bisa menyesatkan! Jadi lebih baik untuk membuatnya sesederhana mungkin.
Saya ingin menekankan sekali lagi bahwa di sini kami tidak ingin mendapatkan formula yang tepat untuk algoritma kami. Kami hanya ingin menunjukkan bagaimana itu tumbuh ketika input tumbuh dan bandingkan dengan algoritma lain dalam arti itu. Kalau tidak, Anda lebih baik menggunakan metode yang berbeda seperti menandai bangku.
sumber