Suurimman kasvavan osasekvenssin löytämisen ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 8. helmikuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 7 muokkausta .

Suurimman kasvavan osajonon löytämisen tehtävänä on löytää pisin kasvava osajono tietystä elementtijonosta.

Ongelman selvitys

Huomaa, että osasekvenssi ei välttämättä ole osamerkkijono (eli sen elementit eivät välttämättä ole peräkkäisiä alkuperäisessä sekvenssissä). Muodollisesti merkkijonolle x , jonka pituus on n , on tarpeen löytää maksimiluku l ja sitä vastaava kasvava indeksien sarja , jolloin . Suurimmalla kasvavalla osasekvenssillä on sovelluksia fysiikassa, matematiikassa, ryhmäesitysteoriassa, satunnaismatriisiteoriassa. Yleensä tämän ongelman ratkaisu tunnetaan ajassa n log n pahimmassa tapauksessa [1] .

Aiheeseen liittyvät algoritmit

Esimerkki tehokkaasta algoritmista

Esitetään algoritmi ongelman ratkaisemiseksi, joka suoritetaan O( n log n ).

Merkkijonolle x tallennetaan taulukot M ja P , joiden pituus on n . M[i] sisältää tässä vaiheessa löydettyjen kasvavien osasekvenssien x n j , joiden pituus on i , , pienimmän viimeisistä alkioista . P[i] tallentaa edellisen merkin indeksin pisimmälle nousevalle osasekvenssille, joka päättyy i:nnen paikkaan. Jokaisessa vaiheessa tallennamme alisekvenssin nykyisen maksimipituuden ja viimeisen merkin vastaavan indeksin, muistaen säilyttää taulukoiden ominaisuudet. Vaihe on siirtymä merkkijonon seuraavaan elementtiin, jokainen siirtymä ei vaadi enempää kuin ajan logaritmi (binäärihaku taulukossa M ).

P = array of length N M = array of length N + 1 L = 0 for i in range 0 to N-1: lo = 1 hi = L while lo ≤ hi: mid = ceil((lo+hi)/2) if X[M[mid]] < X[i]: lo = mid+1 else: hi = mid-1 newL = lo P[i] = M[newL-1] M[newL] = i if newL > L: L = newL S = array of length L k = M[L] for i in range L-1 to 0: S[i] = X[k] k = P[k] return S

On selvää, että algoritmin suorittamisen jälkeen L on halutun osajonon pituus, ja itse elementit voidaan saada laajentamalla P rekursiivisesti indeksielementistä.

Muistiinpanot

  1. Schensted, C. (1961). "Pisin kasvavat ja laskevat osajaksot". Canadian Journal of Mathematics 13: 179-191.
  2. Hunt, James W. ja Szymanski, Thomas G. Nopea algoritmi pisimpien yhteisten osasekvenssien   laskemiseen // Commun . ACM. - ACM, 1977. - Voi. 20 , ei. 5 . - s. 350--353 . — ISSN 0001-0782 .

Linkit