Analisis Waktu Eksekusi Informal
Diperkenalkan| English | Makna |
|---|---|
| run time/rʌn taɪm/ | waktu jalan |
| linear/ˈlɪnɪə/ | linear |
| quadratic/kwɒˈdrætɪk/ | kuadratik |
Menghitung pekerjaan
- Kita mengukur waktu jalan program dengan berapa banyak kali pernyataan utamanya dijalankan.
- Bukan detik (karena bervariasi per mesin) — sebuah jumlah operasi saat input bertambah.
- Lebih banyak operasi untuk ukuran input yang sama → algoritma lebih lambat.
- Ini memungkinkan kita membandingkan algoritma secara adil, tanpa bergantung pada perangkat keras.
Satu perulangan: sekitar n
- Perulangan atas
nitem menjalankan badannya sekitarnkali. - Gandakan input → sekitar ganda pekerjaan. Ini adalah pertumbuhan linear.
- Menjumlahkan array, mencari daftar satu per satu: semuanya sekitar
nlangkah. - Ditulis secara tidak resmi sebagai "orde
n."
Perulangan bersarang: sekitar n²
- Perulangan bersarang atas
nitem menjalankan bagian dalamnya sekitarn × n = n²kali. - Gandakan input → sekitar empat kali pekerjaan. Ini adalah pertumbuhan kuadratik.
- Membandingkan semua pasangan, mengisi grid
n × n: sekitarn²langkah. n²tumbuh jauh lebih cepat daripadansaatnmenjadi besar.
Membandingkan pertumbuhan
- Untuk membandingkan algoritma, tanyakan bagaimana pekerjaan bertambah saat input bertambah.
- Untuk
nyang besar, algoritmanmengalahkan algoritman²— seringkali dengan selisih yang signifikan. - Fokus pada bagian kode yang berjalan paling sering (biasanya perulangan terdalam).
- Suku yang pertumbuhannya paling cepat mendominasi total waktu eksekusi.
Hakimi waktu eksekusi berdasarkan PERTUMBUHAN, bukan jumlah tetap. Algoritma yang melakukan n langkah dan yang melakukan 2n + 5 langkah keduanya tumbuh linearly — untuk perbandingan, konstanta dan +5 tidak penting; bentuknya (n vs n²) yang penting. Satu perulangan sekitar n; perulangan bersarang sekitar n², yang tumbuh jauh lebih cepat untuk input besar.
Dua cara untuk menemukan duplikat dalam n item:
- Perulangan bersarang membandingkan setiap pasangan: sekitar
n²langkah. - Urutkan dulu, lalu satu kali lewati: jauh lebih sedikit langkah untuk
nbesar. - Untuk
n = 1000,n²adalah satu juta langkah — pendekatann²jauh lebih lambat.
Analisis waktu eksekusi informal menghitung berapa kali pernyataan dijalankan saat input bertambah. Satu perulangan atas n item adalah sekitar n (linear); perulangan bersarang adalah sekitar n² (kuadratik), yang tumbuh jauh lebih cepat. Bandingkan algoritma berdasarkan pertumbuhannya, fokus pada kode yang dieksekusi paling banyak (terdalam).
How the work grows with n
Perulangan bersarang (n²) tumbuh jauh lebih cepat daripada perulangan tunggal (n).
Perulangan tunggal atas n item menjalankan tubuhnya sekitar berapa kali?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Satu perulangan atas n item → sekitar n langkah (linear).
Perulangan bersarang atas n item menjalankan tubuh dalamnya sekitar berapa kali?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
n × n = n² (quadratic).
Untuk n = 1000, sekitar berapa banyak langkah algoritma n² (dalam juta)?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
1000² = 1,000,000 = 1 million.
Untuk n besar, algoritma n-langkah umumnya lebih cepat daripada yang n²-langkah.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
n² tumbuh jauh lebih cepat, sehingga melakukan jauh lebih banyak pekerjaan pada n besar.
Kami mengukur waktu berjalan dalam detik, yang sama di setiap komputer.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Kami menghitung operasi vs. ukuran input — detik bervariasi tergantung mesin.