Inversioiden laskeminen muokatulla merge sort -algoritmilla
Laskekaa taulukon inversioiden määrä — parien, joissa a[i] > a[j] ja i < j — laskemalla ositusten väliset inversiot yhdistämisvaiheen aikana.
Inversioiden laskeminen muokatulla merge sort -algoritmilla on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/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.
Mikä on inversio?
Inversio taulukossa on indeksipari (i, j), jossa i < j, mutta a[i] > a[j] — suurempi alkio esiintyy ennen pienempää. Esimerkiksi taulukossa [3, 1, 2] inversiot ovat (3,1) ja (3,2), joten niitä on yhteensä 2. Järjestetyssä taulukossa on 0 inversiota. Käänteisesti järjestetyssä n alkion taulukossa on n(n-1)/2 inversiota. Inversioiden määrä kertoo, kuinka kaukana taulukko on järjestyksestä.
arr = [3, 1, 2]
# Inversions: pairs (i,j) where i<j and arr[i]>arr[j]
inversions = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
inversions.append((arr[i], arr[j]))
print('Inversions in', arr, ':', inversions)
print('Count:', len(inversions)) # 2
# Maximum inversions in n-element array:
import math
n = 5
print(f'Max inversions for n={n}: {n*(n-1)//2}') # 10 for [5,4,3,2,1]Naiivi O(n²)-lähestymistapa
Raakavoimainen menetelmä käy läpi kaikki parit (i, j), joille i < j, ja laskee ne parit, joissa a[i] > a[j]. Sen aikavaativuus on O(n²) ja tilavaativuus O(1). Kun n = 10⁵, tämä tarkoittaa 5 × 10⁹ vertailua, mikä on liian hidasta. Muokattuun lomituslajitteluun perustuva hajota ja hallitse -menetelmä ratkaisee ongelman ajassa O(n log n). Keskeinen oivallus on, että lomituslajittelun aikana voimme laskea puoliskojen väliset inversiot tehokkaasti lomitusvaiheessa.
def count_inversions_brute(arr):
n = len(arr)
count = 0
for i in range(n):
for j in range(i + 1, n):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_brute([3, 1, 2])) # 2
print(count_inversions_brute([5, 4, 3, 2, 1])) # 10
print(count_inversions_brute([1, 2, 3, 4, 5])) # 0
print(count_inversions_brute([2, 4, 1, 3, 5])) # 3Lomituslajittelun oivallus
Kahden järjestetyn puoliskon L ja R lomituksessa, jos valitsemme alkion R[j] ennen alkiota L[i], koska R[j] < L[i], kaikki L:n jäljellä olevat alkiot indeksistä i alkaen ovat myös suurempia kuin R[j]. Tämä johtuu siitä, että L on järjestetty. Siksi aina, kun otamme alkion oikeasta puoliskosta, laskemme len(L) - i puoliskojen välistä inversiota. Tämä laskenta tapahtuu normaalin lomituksen yhteydessä käytännössä ilman lisäkustannuksia.
# During merge of [1, 3, 5] and [2, 4, 6]:
# Compare L[0]=1 vs R[0]=2: take L[0]=1, no inversions
# Compare L[1]=3 vs R[0]=2: take R[0]=2, inversions += len(L)-1 = 2 (3>2, 5>2)
# Compare L[1]=3 vs R[1]=4: take L[1]=3, no inversions
# Compare L[2]=5 vs R[1]=4: take R[1]=4, inversions += len(L)-2 = 1 (5>4)
# Compare L[2]=5 vs R[2]=6: take L[2]=5, no inversions
# Take R[2]=6
# Total cross-inversions = 2 + 1 = 3
print('Cross-inversions identified during merge: 3')Muokatun lomituslajittelun toteutus
Muokatkaa lomituslajittelua niin, että se palauttaa sekä järjestetyn taulukon että inversioiden määrän. Inversioiden kokonaismäärä = vasemman puoliskon inversiot + oikean puoliskon inversiot + lomituksessa löydetyt puoliskojen väliset inversiot. Perustapaus palauttaa yhden alkion ja 0 inversiota. Lomitusfunktio laskee inversiot lomituksen aikana. Kokonaisaikavaativuus: O(n log n).
def count_inversions(arr):
def merge_sort_count(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_count = merge_sort_count(arr[:mid])
right, right_count = merge_sort_count(arr[mid:])
merged, cross_count = merge_count(left, right)
return merged, left_count + right_count + cross_count
def merge_count(left, right):
result, count = [], 0
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
count += len(left) - i # all remaining in left are inversions
result += left[i:] + right[j:]
return result, count
_, total = merge_sort_count(arr)
return total
print(count_inversions([3, 1, 2])) # 2
print(count_inversions([5, 4, 3, 2, 1])) # 10
print(count_inversions([2, 4, 1, 3, 5])) # 3Algoritmin jäljittäminen
Jäljitetään [2, 4, 1, 3]: jaetaan taulukko osiin [2, 4] ja [1, 3]. Vasemman osan lajittelu: [2, 4] → järjestettynä [2,4], 0 inversiota. Oikean osan lajittelu: [1, 3] → järjestettynä [1,3], 0 inversiota. Lomitetaan [2,4] ja [1,3]: otetaan 1 (count += 2, koska 2>1 ja 4>1), otetaan 2 (määrä ei muutu), otetaan 3 (count += 1, koska 4>3) ja otetaan 4. Puoliskojen välisiä inversioita on 3. Yhteensä = 0+0+3 = 3. Varmistus: parit (2,1), (4,1) ja (4,3) muodostavat 3 inversiota. ✓
def count_with_trace(arr):
def ms(arr, depth=0):
indent = ' ' * depth
if len(arr) <= 1: return arr, 0
mid = len(arr) // 2
L, lc = ms(arr[:mid], depth+1)
R, rc = ms(arr[mid:], depth+1)
merged, cc = merge_c(L, R)
print(f'{indent}merge({L},{R}) → cross={cc}')
return merged, lc + rc + cc
def merge_c(L, R):
res, c, i, j = [], 0, 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]: res.append(L[i]); i += 1
else: res.append(R[j]); j += 1; c += len(L) - i
return res + L[i:] + R[j:], c
_, total = ms(arr)
return total
print('Total inversions:', count_with_trace([2, 4, 1, 3]))Miksi puoliskojen väliset inversiot lasketaan oikein
Oikeellisuus: jokainen inversiopari (a[i], a[j]), jossa i < j, kuuluu täsmälleen yhteen kolmesta luokasta: (1) Molemmat alkiot ovat vasemmassa puoliskossa — vasemman puoliskon rekursiivinen kutsu laskee ne. (2) Molemmat alkiot ovat oikeassa puoliskossa — oikean puoliskon rekursiivinen kutsu laskee ne. (3) Vasemman puoliskon alkio on suurempi kuin oikean puoliskon alkio — inversio lasketaan lomituksessa puoliskojen välisenä inversiona. Luokat ovat toisensa poissulkevia ja kattavat kaikki tapaukset, joten yhtäkään inversiota ei lasketa kahdesti eikä yksikään jää laskematta. Tämä ositusargumentti on hajota ja hallitse -menetelmän tavanomainen oikeellisuustodistus.
# Verification: compare with brute force on random arrays
import random
def count_brute(arr):
n = len(arr)
return sum(1 for i in range(n) for j in range(i+1,n) if arr[i]>arr[j])
def count_dc(arr):
def ms(a):
if len(a)<=1: return a, 0
m=len(a)//2
L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr)[1]
for _ in range(100):
arr = random.choices(range(20), k=random.randint(1,10))
assert count_dc(arr[:]) == count_brute(arr), 'MISMATCH!'
print('All 100 random tests passed!')Inversioiden laskennan sovelluksia
Inversiot mittaavat järjestyksenmukaisuutta. Sovelluksia: (1) Järjestyskorrelaatio: kahden järjestetyn listan välinen Kendallin taun etäisyys on inversioiden määrä. (2) Lisäyslajittelun tehokkuus: lisäyslajittelu tekee täsmälleen yhtä monta vaihtoa kuin inversioita on. (3) Kuplalajittelun analyysi: jokainen kuplalajittelun kierros vähentää inversioiden määrää; tarvittavien kierrosten määrä on yhtä suuri kuin inversioiden määrä. (4) Pulmien ratkaistavuus: 8-puzzle tai 15-puzzle on ratkaistavissa täsmälleen silloin, kun inversioiden määrällä on tietty pariteetti.
# Kendall tau: number of inversions between two rankings
# Useful for comparing search result rankings or recommendation systems
def kendall_tau(rank1, rank2):
'''Count inversions where rank1 and rank2 disagree on relative order.'''
# Map rank2 positions to create a comparison sequence
pos = {v: i for i, v in enumerate(rank2)}
# Convert rank1 to position-in-rank2 ordering
arr = [pos[v] for v in rank1]
return count_inversions(arr)
def count_inversions(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]
print(kendall_tau([1,2,3],[3,1,2])) # measures disagreementAiheeseen liittyvä: Count Smaller Numbers After Self
Count Smaller Numbers After Self (LeetCode 315) kysyy jokaisesta alkiosta, kuinka monta sitä oikealla puolella pienempää alkiota on. Tämä on alkiokohtaista inversioiden laskentaa. Ongelma voidaan ratkaista samalla muokatulla lomituslajittelulla, kun seurataan, mitkä alkuperäiset indeksit lasketaan mukaan. Vaihtoehtoisesti voidaan käyttää Binary Indexed Tree -rakennetta (Fenwick Tree) tai indeksien seurantaa hyödyntävää lomituslajittelua. Hajota ja hallitse -menetelmän aikavaativuus on O(n log n).
def count_smaller(nums):
n = len(nums)
result = [0] * n
indexed = list(enumerate(nums))
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i][1] <= right[j][1]:
# left[i] is placed; j elements from right are smaller and to the right
result[left[i][0]] += j
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
while i < len(left):
result[left[i][0]] += j # all of right is smaller
merged.append(left[i]); i += 1
return merged + right[j:]
merge_sort(indexed)
return result
print(count_smaller([5, 2, 6, 1])) # [2, 1, 1, 0]Reverse Pairs
Reverse Pairs (LeetCode 493) laskee parit (i, j), joille i < j ja nums[i] > 2 × nums[j]. Tavallisessa inversioiden laskennassa käytetään ehtoa nums[i] > nums[j]. Tässä kynnys muuttuu muotoon 2 × nums[j]. Muokatkaa lomituslajittelua siten, että laskette puoliskojen väliset parit ennen lomitusta kahden osoittimen avulla, kun vasemmassa puoliskossa on vielä kelvollisia alkioita, ja suoritatte sitten lomituksen normaalisti. Kokonaisaikavaativuus on O(n log n).
def reverse_pairs(nums):
def merge_sort_count(arr):
if len(arr) <= 1: return arr, 0
mid = len(arr) // 2
L, lc = merge_sort_count(arr[:mid])
R, rc = merge_sort_count(arr[mid:])
# Count cross pairs: L[i] > 2*R[j]
j = 0
cross = 0
for l_val in L:
while j < len(R) and l_val > 2 * R[j]:
j += 1
cross += j
# Normal merge (separate from count)
merged = []
i = jj = 0
while i < len(L) and jj < len(R):
if L[i] <= R[jj]: merged.append(L[i]); i += 1
else: merged.append(R[jj]); jj += 1
merged += L[i:] + R[jj:]
return merged, lc + rc + cross
return merge_sort_count(nums)[1]
print(reverse_pairs([1, 3, 2, 3, 1])) # 2
print(reverse_pairs([2, 4, 3, 5, 1])) # 3Globaalien ja paikallisten inversioiden määrän vertailu
Globaalit ja paikalliset inversiot (LeetCode 775): Annettuna on lukujen 0..n-1 permutaatio. Määrittäkää, ovatko globaalien inversioiden (kaikki parit i<j, joille a[i]>a[j]) määrä ja paikallisten inversioiden (vierekkäiset parit) määrä samat. Keskeinen havainto: jokainen paikallinen inversio on myös globaali, joten globaalien inversioiden määrä ≥ paikallisten inversioiden määrä. Ne ovat samat täsmälleen silloin, kun ei ole ei-vierekkäisiä inversioita – toisin sanoen mikään alkio ei ole yli yhden paikan päässä järjestetyn taulukon mukaisesta indeksistään. Tämä voidaan pelkistää tarkistamaan abs(a[i] - i) ≤ 1 kaikilla i:n arvoilla.
def is_ideal_permutation(A):
'''Global inversions == local inversions
iff no element is more than 1 position from its sorted index.'''
return all(abs(a - i) <= 1 for i, a in enumerate(A))
print(is_ideal_permutation([1, 0, 2])) # True
print(is_ideal_permutation([1, 2, 0])) # False (A[0]=1 is far from 2, A[2]=0 is far)
# Verification with inversion counts
print(count_inversions([1, 0, 2])) # 1 (global)
local1 = sum(1 for i in range(len([1,0,2])-1) if [1,0,2][i]>[1,0,2][i+1])
print('local:', local1) # 1 (equal)
def count_inversions(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]Inversioiden määrän laskennan kompleksisuusyhteenveto
Yhteenveto: brute force -menetelmä laskee inversiot ajassa O(n²). Muokattu yhdistämislajittelu saavuttaa ajan O(n log n) laskemalla puoliskojen väliset inversiot yhdistämisvaiheen aikana. Lisäkustannus on O(1) kutakin vertailua kohden (lisätään len(left) - i), joten kokonaislisäkustannus on O(n) kullakin yhdistämislajittelun tasolla — sama kuin tavallisessa yhdistämislajittelussa. Aputaulukoiden tilantarve on O(n). Tämä on klassinen esimerkki D&C:n käyttämisestä järjestystilastojen laskemiseen lineaaris-logaritmisessa ajassa.
import time, random
def time_method(func, arr):
start = time.time()
result = func(arr[:])
return result, time.time() - start
def count_brute(arr):
return sum(1 for i in range(len(arr)) for j in range(i+1,len(arr)) if arr[i]>arr[j])
def count_dc(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2;L,lc=ms(a[:m]);R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]
arr = random.sample(range(1000), 1000)
r1, t1 = time_method(count_brute, arr)
r2, t2 = time_method(count_dc, arr)
print(f'Brute: {r1} in {t1:.4f}s')
print(f'D&C: {r2} in {t2:.4f}s')
print(f'Speedup: {t1/t2:.1f}x')Pikatesti
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheista.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte: inversiot mittaavat, kuinka epäjärjestyksessä taulukko on, ja niiden laskeminen vie brute force -menetelmällä O(n²) ja D&C-menetelmällä O(n log n), muokattu yhdistämislajittelu laskee puoliskojen väliset inversiot lisäämällä len(left)-i aina, kun oikeanpuoleinen alkio valitaan vasemmanpuoleisen alkion sijaan ja oikeellisuus perustuu ositukseen: vasemman puoliskon sisäiset, oikean puoliskon sisäiset ja puoliskojen väliset inversiot ovat erillisiä ja kattavat yhdessä kaikki inversiot. Seuraavaksi tutustumme enemmistöalkion löytämiseen tarkoitettuun Boyer-Moore-äänestysalgoritmiin.
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 ”Inversioiden laskeminen muokatulla merge sort -algoritmilla” ilmainen?
Kyllä – oppitunnin ”Inversioiden laskeminen muokatulla merge sort -algoritmilla” 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 ”Inversioiden laskeminen muokatulla merge sort -algoritmilla”?
Laskekaa taulukon inversioiden määrä — parien, joissa a[i] > a[j] ja i < j — laskemalla ositusten väliset inversiot yhdistämisvaiheen aikana. 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 2/4.
Kuinka kauan ”Inversioiden laskeminen muokatulla merge sort -algoritmilla”-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