Teorem induk lanjutan untuk rekursi bahagi-dan-takluk

Divide and Conquer ialah algoritma berdasarkan penguraian secara rekursif masalah kepada berbilang sub-masalah jenis yang serupa, dan sub-masalah ini boleh diselesaikan dengan mudah.

Contoh

Mari kita ambil contoh untuk memahami teknik divide and conquer dengan lebih mendalam -

function recursive(input x size n)
   if(n < k)
      Divide the input into m subproblems of size n/p.
      and call f recursively of each sub problem
   else
      Solve x and return

Gabungkan hasil semua submasalah dan kembalikan penyelesaian kepada masalah asal.

Penjelasan masalah di atas − Dalam set masalah akan dibahagikan kepada submasalah yang lebih kecil yang boleh diselesaikan dengan mudah.

Teorem Sarjana untuk bahagi dan menakluk ialah teorem analisis yang boleh digunakan untuk menentukan nilai besar-0 untuk algoritma hubungan rekursif masa yang diperlukan oleh algoritma dan mewakilinya dalam bentuk notasi asimptotik.

Contoh nilai masa jalan masalah dalam contoh di atas −

T(n) = f(n) + m.T(n/p)

Untuk kebanyakan algoritma rekursif, anda akan dapat mencari kerumitan Masa Untuk algoritma menggunakan teorem induk, tetapi terdapat beberapa kes teorem induk mungkin tidak terpakai Ini adalah kes di mana teorem induk tidak terpakai Apabila masalah T(n) tidak monoton, contohnya, T(n) = sin n . Fungsi masalah f(n) bukan polinomial bentuk −

T(n) = aT(n/b) + ø((n^k)logpn)

di mana n ialah saiz masalah.

a = bilangan submasalah dalam rekursi, a > 0

n/b = saiz setiap submasalah b > 0, p ialah nombor nyata.

Untuk menyelesaikan masalah jenis ini kita akan menggunakan penyelesaian berikut:

Jika a > b

k
• , maka T(n) = ∅ (nlogba)Jika a = b
k
• , maka Jika p > -1, maka T(n) = ∅(nlogba log
  p+1
  • n)Jika p = -1, maka T(n) = ∅(nlog
  ba
  • loglogn) Jika p ba
  • )
  Jika a k
• , maka Jika p > = ∅ (n
  k
  • log_pn)Jika p
Menggunakan algoritma induk lanjutan, kami akan mengira kerumitan sesetengah algoritma −

Carian binari

− t(n) = θ(logn)

Isih gabung − T(n) = θ(nlogn)

Atas ialah kandungan terperinci Teorem induk lanjutan untuk rekursi bahagi-dan-takluk. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!