Langsung ke konten
Brute force dulu

Pelajaran 3.2

Hitung langkahnya

6 menit · 7 langkah

  1. Langkah 1 dari 7 · Penjelasan

    Satu loop di atas n item kira-kira butuh n langkah. Dua loop bersarang di atas item yang sama butuh sekitar n × n langkah. Itu ditulis O(n²).

    Untuk 10 item, bedanya kecil: 10 lawan 100. Untuk 100.000 item, bedanya 100.000 lawan 10.000.000.000. Makin besar n, makin jauh n² meninggalkan n.

  2. Langkah 2 dari 7 · Tebak hasilnya

    Berapa nilai steps di akhir untuk n = 6?

    function solution(n) {  let steps = 0  for (let i = 0; i < n; i++) {    for (let j = 0; j < n; j++) {      steps++    }  }  return steps}
    1. 36
    2. 12
    3. 21
    4. 6

  3. Langkah 3 dari 7 · Tebak hasilnya

    Dua loop, tapi tidak bersarang. Apa yang di-return untuk n = 5?

    function solution(n) {  let steps = 0  for (let i = 0; i < n; i++) steps++  for (let j = 0; j < n; j++) steps++  return steps}
    1. 10
    2. 25
    3. 5

  4. Langkah 4 dari 7 · Tebak hasilnya

    Loop yang membagi dua. Apa yang di-return untuk n = 64?

    function solution(n) {  let steps = 0  while (n > 1) {    n = Math.floor(n / 2)    steps++  }  return steps}
    1. 6
    2. 32
    3. 63

  5. Langkah 5 dari 7 · Pilih pendekatan

    n = 10⁵. Kamu mengecek semua pasangan dengan j = i + 1, sekitar 5 × 10⁹ cek. Anggap komputer menjalankan sekitar 10⁸ langkah sederhana per detik, dan batas waktunya beberapa detik.
    Apa yang terjadi?

    1. Terlalu lambat. Sekitar 50 detik, jadi tes kena timeout
    2. Aman, komputer sekarang sangat cepat
    3. Aman, karena j = i + 1 sudah memotong pekerjaannya

  6. Langkah 6 dari 7 · Pilih pendekatan

    Mana yang O(n²)?

    1. Loop di atas nums, dan di dalamnya nums.includes(x)
    2. Dua loop di atas nums, satu setelah yang lain
    3. Loop while yang membagi n dua setiap putaran
    4. Loop di atas nums yang membaca nums[i - 1]

  7. Langkah 7 dari 7 · Ringkasan

    • Loop bersarang mengalikan, loop berurutan menjumlahkan.
    • Membagi dua setiap putaran itu O(log n), sangat sedikit langkah.
    • Hati-hati dengan loop tersembunyi seperti includes, indexOf, dan slice di dalam loop.
    • Patokan kasar sekitar 10⁸ langkah sederhana per detik.

    Kartu pola

    Hitung langkah
    Kapan dipakai: Sebelum ngoding solusi brute force. Kalikan ukuran loop yang bersarang dan bandingkan dengan 10⁸.
    for ... for ...      // n × n  = O(n²)for ...; for ...     // n + n  = O(n)while (n > 1) n /= 2 // O(log n)