Hajota ja hallitse -malli
Poimikaa kolmivaiheinen malli (jaa, ratkaise, yhdistä) merge sort -algoritmista ja soveltakaa sitä järjestelmällisesti uudenlaisiin ongelmiin.
Hajota ja hallitse -malli on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä hajota ja hallitse tarkoittaa?
Hajota ja hallitse (D&C) ratkaisee ongelman jakamalla sen samantyyppisiin toisistaan riippumattomiin osaongelmiin, ratkaisemalla kunkin rekursiivisesti ja yhdistämällä ratkaisut. Keskeinen sana on riippumattomiin — osaongelmat eivät jaa tilaa keskenään, toisin kuin dynaamisessa ohjelmoinnissa, jossa ne menevät päällekkäin. Klassisia esimerkkejä ovat lomituslajittelu, binäärihaku, pikalajittelu, lähimpien pisteiden pari ja nopea matriisikertolasku. Hajota ja hallitse saavuttaa yleensä O(n log n) -aikavaativuuden kolmivaiheisen mallin avulla.
# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP: sub-problems OVERLAP (same sub-problem solved multiple times)
# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing
# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
# T(n) = T(n/2) + O(1) → O(log n) [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]Kolmivaiheinen malli
Jokainen D&C-algoritmi noudattaa kolmea vaihetta: (1) Jaa — jaa ongelma kahdeksi tai useammaksi pienemmäksi osaongelmaksi, yleensä keskipisteestä. (2) Ratkaise — ratkaise kukin osaongelma rekursiivisesti. Määritä perustapaus rekursion lopettamiseksi, yleensä n ≤ 1. (3) Yhdistä — yhdistä osaongelmien ratkaisut kokonaisratkaisuksi. Luovuus tarvitaan ennen kaikkea yhdistämisvaiheessa; jakaminen tarkoittaa yleensä vain jakoa keskipisteestä.
def divide_and_conquer(arr, lo, hi):
# BASE CASE: trivial sub-problem
if lo >= hi:
return base_case_result(arr, lo, hi)
# DIVIDE: split at midpoint
mid = (lo + hi) // 2
# CONQUER: solve sub-problems recursively
left_result = divide_and_conquer(arr, lo, mid)
right_result = divide_and_conquer(arr, mid + 1, hi)
# COMBINE: merge results
return combine(left_result, right_result, arr, lo, mid, hi)
def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)Lomituslajittelu hajota ja hallitse -mallin keskeisenä esimerkkinä
Lomituslajittelu havainnollistaa hajota ja hallitse -menetelmää täydellisesti: Jaa taulukko keskipisteestä. Ratkaise lajittelemalla kumpikin puolisko rekursiivisesti. Yhdistä lomittamalla kaksi järjestettyä puoliskoa ajassa O(n). Lomitusvaiheessa tehdään kaikki työ. Rekursioyhtälö on T(n) = 2T(n/2) + O(n). Masterin lauseen tapauksen 2 perusteella: T(n) = O(n log n). Tämä on tärkein hajota ja hallitse -rekursioyhtälö, joka kannattaa opetella ulkoa.
def merge_sort(arr):
# BASE CASE
if len(arr) <= 1:
return arr
# DIVIDE
mid = len(arr) // 2
# CONQUER
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# COMBINE
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
print(merge_sort([5, 3, 8, 1, 9, 2])) # [1,2,3,5,8,9]Masterin lauseen pikaopas
Masterin lause ratkaisee muotoa T(n) = aT(n/b) + f(n) olevat rekursioyhtälöt: Tapaus 1: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). Tapaus 2: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). Tapaus 3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). Lomituslajittelu: a=2, b=2, f(n)=O(n), n^log_2(2)=n → tapaus 2 → O(n log n).
# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n) → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1) → a=2,b=2,f=1,n^1=n >> 1 → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2) → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1) → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree
recurrences = [
('Merge sort: 2T(n/2)+n', 'O(n log n)'),
('Binary search: T(n/2)+1', 'O(log n)'),
('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)Maksimiosataulukko: hajota ja hallitse -lähestymistapa
Hajota ja hallitse -lähestymistavassa osataulukon maksimi on joko kokonaan vasemmassa puoliskossa, kokonaan oikeassa puoliskossa tai ylittää keskipisteen. Keskipisteen ylittävässä tapauksessa laajentakaa vasemmalle kohdasta mid ja oikealle kohdasta mid+1, ottamalla kummastakin suunnasta suurin summa, ja yhdistäkää tulokset. Tämä O(n log n) -aikainen hajota ja hallitse -menetelmä on hitaampi kuin Kadane-algoritmin O(n)-menetelmä, mutta havainnollistaa mallia erinomaisesti ja on yleinen hajota ja hallitse -aiheinen haastattelukysymys.
def max_subarray_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
# Conquer
left_max = max_subarray_dc(nums, lo, mid)
right_max = max_subarray_dc(nums, mid + 1, hi)
# Cross-midpoint sum
left_sum = curr = 0
for i in range(mid, lo - 1, -1):
curr += nums[i]
left_sum = max(left_sum, curr)
right_sum = curr = 0
for i in range(mid + 1, hi + 1):
curr += nums[i]
right_sum = max(right_sum, curr)
cross_max = left_sum + right_sum
return max(left_max, right_max, cross_max)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums)) # 6Potenssifunktio: nopea potenssilaskenta
Fast Power (LeetCode 50): laskekaa x^n ajassa O(log n) hajota ja hallitse -menetelmällä. Jos n on parillinen: x^n = (x^(n/2))^2. Jos n on pariton: x^n = x × x^(n-1). Käsitelkää negatiivinen n kaavalla x^(-n) = 1/x^n. Jokainen rekursiivinen kutsu puolittaa n:n, joten rekursion syvyys on O(log n). Tämä on selkeä esimerkki tapauksesta, jossa yhdistämisvaihe on vain kertolasku — yksinkertainen mutta tehokas.
def my_pow(x, n):
if n < 0:
return 1 / my_pow(x, -n)
# BASE CASE
if n == 0: return 1
# DIVIDE and CONQUER
half = my_pow(x, n // 2)
if n % 2 == 0:
return half * half # even: x^n = (x^(n/2))^2
else:
return x * half * half # odd: x^n = x * (x^(n/2))^2
print(my_pow(2, 10)) # 1024
print(my_pow(2, -2)) # 0.25
print(my_pow(3, 5)) # 243
print(my_pow(0, 0)) # 1Järjestetyn taulukon muuntaminen BST-puuksi
Convert Sorted Array to BST (LeetCode 108) käyttää hajota ja hallitse -menetelmää: valitaan keskipiste juureksi, mikä takaa korkeuden tasapainon, ja rakennetaan vasen alipuu rekursiivisesti vasemmasta puoliskosta ja oikea alipuu oikeasta puoliskosta. Näin syntyy korkeudeltaan tasapainotettu BST, jonka vähimmäiskorkeus on O(log n). Hajota ja hallitse -rakenne muistuttaa binäärihakua — jokaisella rekursion tasolla keskipisteestä tulee nykyisen ala-alueen juuri.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sorted_array_to_bst(nums):
def helper(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid]) # DIVIDE at midpoint
node.left = helper(lo, mid - 1) # CONQUER left
node.right = helper(mid + 1, hi) # CONQUER right
# COMBINE: already done by assignment
return node
return helper(0, len(nums) - 1)
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)
root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root)) # [-10,-3,0,5,9] (sorted, proving BST property)Milloin hajota ja hallitse ei ole paras valinta
Hajota ja hallitse -menetelmällä on lisäkustannuksia: funktiokutsupinon syvyys, taulukon osiin jako, jos indeksejä ei käytetä, sekä yhdistämisvaihe. Menetelmä on optimaalinen, kun yhdistämisvaiheen aikavaativuus on O(n) tai pienempi. Kun osaongelmat menevät päällekkäin, hajota ja hallitse laskee ratkaisuja turhaan uudelleen — tarvitaan dynaamista ohjelmointia. Kun yhdistämisvaihe hallitsee kokonaisuutta, esimerkiksi sen aikavaativuus on O(n²), hajota ja hallitse ei paranna naiiveihin menetelmiin verrattuna. Tietäkää, milloin kumpaakin menetelmää käytetään: hajota ja hallitse toisistaan riippumattomiin osaongelmiin ja dynaaminen ohjelmointi päällekkäisiin osaongelmiin.
# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead
def fib_dc(n):
if n <= 1: return n
return fib_dc(n-1) + fib_dc(n-2) # O(2^n)!
def fib_dp(n):
a, b = 0, 1
for _ in range(n): a, b = b, a+b
return a # O(n)
print(fib_dp(30)) # fast
# fib_dc(40) would take seconds — do not run large values!Hajota ja hallitse järjestetyn matriisin binäärihaussa
Sellaisesta 2D-matriisista etsiminen (LeetCode 240), jossa jokainen rivi ja sarake on järjestetty, voidaan toteuttaa hajota ja hallitse -menetelmällä: aloittakaa oikeasta yläkulmasta. Jos current > target, siirtykää vasemmalle, jolloin sarake poistuu hausta. Jos current < target, siirtykää alas, jolloin rivi poistuu hausta. Jos ne ovat yhtä suuret, alkio on löytynyt. Tämä O(m+n)-aikainen algoritmi ei teknisesti ole rekursiivinen hajota ja hallitse -menetelmä, mutta siinä on sama keskeinen ajatus: puolet hakualueesta poistetaan jokaisella askeleella.
def search_matrix(matrix, target):
if not matrix: return False
m, n = len(matrix), len(matrix[0])
row, col = 0, n - 1 # start top-right
while row < m and col >= 0:
val = matrix[row][col]
if val == target:
return True
elif val > target:
col -= 1 # eliminate this column
else:
row += 1 # eliminate this row
return False
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 20)) # FalseRekursiopuun analyysi
Jos hajota ja hallitse -rekursioyhtälö ei sovi Masterin lauseeseen, käyttäkää rekursiopuu-menetelmää. Piirtäkää rekursiivisten kutsujen jokainen taso ja laskekaa yhteen kullakin tasolla tehtävä työ. Lomituslajittelussa tasolla k on 2^k kappaletta osaongelmia, joiden koko on n/2^k. Yhdellä tasolla tehtävä työ = 2^k × O(n/2^k) = O(n). Tasoja on yhteensä log n. Kokonaistyö = O(n log n). Tämä visuaalinen menetelmä toimii minkä tahansa rekursioyhtälön kanssa ja auttaa ymmärtämään, miksi hajota ja hallitse saavuttaa yleensä O(n log n) -aikavaativuuden.
# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)
import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')Hajota ja hallitse -ratkaisun esittäminen haastattelussa
Kun esittelette hajota ja hallitse -ratkaisua haastattelussa: (1) Ilmaiskaa kolme vaihetta selkeästi: 'Jaan ongelman keskipisteestä, ratkaisen kumpikin puoliskon rekursiivisesti ja yhdistän tulokset lomittamalla.' (2) Määrittäkää perustapaus selkeästi. (3) Johtakaa rekursioyhtälö: T(n) = 2T(n/2) + O(n). (4) Johtakaa O(n log n) Masterin lauseen tai rekursiopuun avulla. (5) Mainitkaa, milloin hajota ja hallitse on vaihtoehtoja parempi tai huonompi, esimerkiksi dynaaminen ohjelmointi päällekkäisiin osaongelmiin ja Kadane-algoritmi maksimiosataulukkoon.
# D&C interview template to memorize:
def dc_template(problem, lo, hi):
# 1. BASE CASE (state it first)
if lo == hi: return solve_base(problem, lo)
# 2. DIVIDE
mid = (lo + hi) // 2
# 3. CONQUER
left = dc_template(problem, lo, mid)
right = dc_template(problem, mid + 1, hi)
# 4. COMBINE (this is where the algorithm-specific logic goes)
return combine_results(left, right, problem, lo, mid, hi)
def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)
print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')Pikatesti
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheista.
Oppitunnin yhteenveto
Tällä oppitunnilla opitte: hajota ja hallitse noudattaa kaavaa: perustapaus → jako keskipisteestä → rekursiivinen ratkaisu → yhdistäminen, T(n) = 2T(n/2) + O(n) antaa Masterin lauseen tapauksen 2 perusteella tuloksen O(n log n) sekä hajota ja hallitse sopii parhaiten toisistaan riippumattomiin osaongelmiin, kun taas dynaamista ohjelmointia tarvitaan päällekkäisiin osaongelmiin. Seuraavaksi sovellamme hajota ja hallitse -menetelmää taulukon inversioiden laskemiseen muokatun lomituslajittelun avulla.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Hajota ja hallitse -malli” ilmainen?
Kyllä – oppitunnin ”Hajota ja hallitse -malli” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Hajota ja hallitse -malli”?
Poimikaa kolmivaiheinen malli (jaa, ratkaise, yhdistä) merge sort -algoritmista ja soveltakaa sitä järjestelmällisesti uudenlaisiin ongelmiin. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Hajota ja hallitse -malli”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Hajota ja hallitse -malli
- Inversioiden laskeminen muokatulla merge sort -algoritmilla
- Enemmistöalkio: Boyer-Moore-äänestys
- Kahden järjestetyn taulukon mediaani