Asymptotiska uppskattningar online. Asymptotisk utvärdering av algoritmen

Analys av jämförelse av tidskostnader för algoritmer utförda för att lösa en instans av ett visst problem, med stora mängder indata, kallas asymptotisk. Algoritmen med den lägre asymptotiska komplexiteten är den mest effektiva.

I asymptotisk analys, algoritmens komplexitetär en funktion som låter dig bestämma hur snabbt algoritmens gångtid ökar med ökande datavolym.

De viktigaste tillväxtuppskattningarna som finns i asymptotisk analys är:

Ο (O-big) – övre asymptotisk uppskattning för tillväxten av tidsfunktionen;
Ω (Omega) – lägre asymptotisk uppskattning för tillväxten av tidsfunktionen;
Θ (Theta) – nedre och övre asymptotiska uppskattningar för tillväxten av tidsfunktionen.

Låta n– mängden data. Sedan tillväxten av algoritmfunktionen f(n) kan du begränsa funktionerna g(n) asymptotiskt:

Till exempel beror tiden för att städa ett rum linjärt på området i samma rum (Θ( S)), dvs med ökande yta i n gånger kommer också städtiden att öka med n en gång. Att slå upp ett namn i telefonboken kommer att ta linjär tid Ο (n), om du använder en linjär sökalgoritm, eller tid som logaritmiskt beror på antalet poster ( Ο (logg 2 ( n))), vid användning av binär sökning.

Av största intresse för oss är Ο -fungera. Dessutom kommer komplexiteten hos algoritmerna i efterföljande kapitel endast att ges för den asymptotiska övre gränsen.

Under frasen "algoritmens komplexitet är Ο (f(n))" antyds det att med en ökning av volymen av indata n, kommer algoritmens gångtid att öka inte snabbare än någon konstant multiplicerad med f(n).

Viktiga regler för asymptotisk analys:

O(k*f) = O(f) – konstant faktor k(konstant) förkastas eftersom volymen data växer förloras dess betydelse, till exempel:

O(9,1n) = O(n)

O(f*g) = O(f)*O(g) – uppskattningen av komplexiteten hos produkten av två funktioner är lika med produkten av deras komplexitet, till exempel:

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2)

O(f/g)=O(f)/O(g) – uppskattningen av komplexiteten för kvoten för två funktioner är lika med kvoten av deras komplexitet, till exempel:

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

O(f+g) är lika med dominant O(f) Och O(g) – en uppskattning av komplexiteten för en summa av funktioner definieras som en uppskattning av komplexiteten hos den dominanta av de första och andra termerna, till exempel:

O(n 5 +n 10) = O(n 10)

Att räkna antalet operationer är tråkigt och, viktigare, inte alls nödvändigt. Baserat på reglerna som anges ovan, för att bestämma komplexiteten hos en algoritm, är det inte nödvändigt, som vi gjorde tidigare, att räkna alla operationer, det räcker att veta vilken komplexitet en viss algoritmdesign (operatör eller grupp av operatörer) har. Således har en algoritm som inte innehåller loopar och rekursioner konstant komplexitet O(1). Komplexiteten i slingexekveringen n iterationer är lika med O(n). Konstruktionen av två kapslade slingor beroende på samma variabel n, har kvadratisk komplexitet O(n 2).

Olika tillvägagångssätt kan användas för att utvärdera prestanda hos algoritmer. Det enklaste är att helt enkelt köra varje algoritm på flera uppgifter och jämföra exekveringstiden. Ett annat sätt är att matematiskt uppskatta exekveringstiden genom att räkna operationer.

Låt oss överväga en algoritm för att beräkna värdet av ett gradpolynom n V given poäng x.
P n (x) = a n x n + a n-1 x n-1 + ... + a i x i + ... + a 1 x 1 + a 0

Algoritm 1- för varje term, utom en 0, konstruktion x V given examen successiv multiplikation och multiplicera sedan med koefficienten. Lägg sedan till villkoren.

Beräkning i termin ( i=1..n) kräver i multiplikationer Alltså totalt 1 + 2 + 3 + ... + n = n(n+1)/2 multiplikationer Dessutom krävs det n+1 tillägg. Total n(n+1)/2 + n + 1= n 2 /2 + 3n/2 + 1 operationer.

Algoritm 2- vi tar ut den x-s utanför parentes och skriv om polynomet i formen
P n (x) = a 0 + x(a 1 + x(a 2 + ... (a i + .. x(a n-1 + a n x)))).

Till exempel,
P 3 (x) = a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 = a 0 + x(a 1 + x(a 2 + a 3 x))

Vi kommer att utvärdera uttrycket från insidan. Den innersta parentesen kräver 1 multiplikation och 1 addition. Dess värde används för nästa parentes... Och så, 1 multiplikation och 1 addition för varje parentes, vilket... n-1 sak. Och efter att ha beräknat den yttersta parentesen, multiplicera med x och addera en 0. Total n multiplikationer + n tillägg = 2n operationer.

Ofta krävs inte en sådan detaljerad bedömning. Istället ger de bara den asymptotiska ökningshastigheten i antalet operationer när n ökar.

Funktion f(n) = n 2/2 + 3n/2 + 1ökar ungefär som n 2/2(vi förkastar den relativt långsamt växande termen 3n/2+1). Konstant faktor 1/2 Vi tar också bort och erhåller en asymptotisk uppskattning för Algoritm 1, som betecknas speciell karaktär O(n 2)[läses som "O stora från en kvadrat"].

Detta är en övre uppskattning, dvs antalet operationer (och därmed drifttiden) växer inte snabbare än kvadraten på antalet element. För att få en känsla för hur detta är, titta på tabellen, som visar siffror som illustrerar tillväxttakten för flera olika funktioner.

		*nlog n**
1	0	0	1
16	4	64	256
256	8	2,048	65,536
4,096	12	49,152	16,777,216
65,536	16	1,048,565	4,294,967,296
1,048,576	20	20,969,520	1,099,301,922,576
16,775,616	24	402,614,784	281,421,292,179,456

Om vi antar att siffrorna i tabellen motsvarar mikrosekunder, då för ett problem med n=1048576 delar av algoritmen med körtid O(log n) det kommer att ta 20 mikrosekunder, algoritmen kommer så småningom På)- 17 minuter, och algoritmen med drifttid O(n 2)- mer än 12 dagar... Nu fördelen med algoritm 2 med utvärdering På) innan Algoritm 1 är ganska uppenbart.

Den bästa uppskattningen är O(1)... I det här fallet beror tiden inte alls på n, dvs konstant för ett godtyckligt antal element.

Således, O()- en "avkortad" uppskattning av algoritmens gångtid, som ofta är mycket lättare att få fram än den exakta formeln för antalet operationer.

Så låt oss formulera två regler för att bilda O()-uppskattningen.

Vid utvärdering av en funktion tas det antal operationer som ökar snabbast som funktion.
Det vill säga om i ett program en funktion, till exempel multiplikation, exekveras På) tider och tillägg - O(n 2) gånger, då är programmets totala komplexitet O(n 2), sedan i slutändan med ökande n snabbare (vid en viss konstant antal gånger) kommer tillägg att utföras så ofta att de kommer att påverka prestandan mycket mer än långsamma men sällsynta multiplikationer. Symbol O() visar uteslutande asymptotiska!

Vid utvärdering av O() tas inte hänsyn till konstanter.
Låt en algoritm utföra 2500n + 1000 operationer och en annan - 2n+1. De har båda ett betyg På), eftersom deras utförandetid växer linjärt.

I synnerhet om båda algoritmerna, t.ex. O(n*log n), betyder det inte att de är lika effektiva. Den första kan vara 1000 gånger mer effektiv. O() betyder helt enkelt att deras tid ökar ungefär som en funktion n*log n.

En annan konsekvens av att utelämna konstanten är algoritmen över tid O(n 2) kan fungera mycket snabbare än algoritmen På) för litet n... På grund av det faktum att det faktiska antalet operationer av den första algoritmen kan vara n2 + 10n + 6, och den andra - 1000000n + 5. Den andra algoritmen kommer dock förr eller senare att gå om den första... n 2 växer mycket snabbare 1000000n.

Logaritmbas inuti symbolen O() inte skriven.
Anledningen till detta är ganska enkel. Låt oss ha O(log2n). Men log 2 n=log 3 n/log 3 2, A logga 3 2, som alla konstanter, är asymptotik en symbol HANDLA OM() tar inte hänsyn till. Således, O(log2n) = O(log 3 n).

Vi kan flytta till vilken bas som helst på samma sätt, vilket betyder att det inte är någon idé att skriva det.

Matematisk tolkning av O()-symbolen.

Definition
O(g)- många funktioner f, för vilka sådana konstanter finns C Och N, Vad |f(x)|<= C|g(x)| för alla x>N.
Spela in f = O(g) betyder bokstavligen det f tillhör uppsättningen O(g). I det här fallet det omvända uttrycket O(g) = f inte vettigt.

I synnerhet kan vi säga det f(n) = 50n tillhör O(n 2). Här har vi att göra med en felaktig uppskattning. Självklart f(n)<= 50n 2 på n>1, men ett starkare uttalande vore f(n) = O(n), sedan för C=50 Och N=1 höger f(n)<= Cn, n>N.

Andra typer av bedömningar.

Tillsammans med bedömningen På) bedömning används Ω(n)[läs som "Omega big from sv"]. Det betecknar den nedre gränsen för tillväxten av funktionen. Låt till exempel antalet operationer av algoritmen beskrivas av funktionen f(n) = Ω(n 2). Detta innebär att även i det mest framgångsrika fallet kommer åtminstone en storleksordning att produceras n 2 handlingar.
...Medan poängen f(n) = O(n 3) garanterar att det i värsta fall blir ordning och reda n 3, inte mer.

Uppskattning används också Θ(n)["Theta from en"], som är en hybrid O() Och Ω() .
Θ(n 2)är både en övre och en nedre asymptotisk uppskattning samtidigt - den kommer alltid att hålla i storleksordningen n 2 operationer. Kvalitet Θ() finns bara när O() Och Ω() sammanfalla och lika med dem.

För de polynomberäkningsalgoritmer som diskuterats ovan är uppskattningarna som hittats samtidigt O(), Ω() Och Θ() .
Om vi lägger till den första algoritmen för att kontrollera x=0 i exponentiering, sedan på de mest framgångsrika initiala data (när x=0) vi har ordning n kontroller, 0 multiplikationer och 1 addition, vilket ger en ny uppskattning Ω(n) tillsammans med den gamla O(n 2).

Som regel ägnas den största uppmärksamheten fortfarande åt den övre skattningen O(), så trots "förbättringen" förblir Algoritm 2 att föredra.

Så, O()- asymptotisk utvärdering av algoritmen på de sämsta indata, Ω() - på bästa indata, Θ() - förkortad notation av detsamma O() Och Ω() .

Trots det faktum att tidskomplexitetsfunktionen för en algoritm kan bestämmas exakt i vissa fall, är det i de flesta fall meningslöst att leta efter dess exakta värde. Faktum är att, för det första, det exakta värdet av tidskomplexitet beror på definitionen av elementära operationer (till exempel kan komplexitet mätas i antalet aritmetiska operationer eller operationer på en Turing-maskin), och för det andra, som storleken på indata ökar, bidraget av konstanta faktorer och villkoren för lägre ordningar som förekommer i uttrycket för den exakta drifttiden blir ytterst obetydliga.

Asymptotisk komplexitet- beaktande av stora indata och bedömning av tillväxtordningen för algoritmens drifttid. Vanligtvis är en algoritm med lägre asymptotisk komplexitet mer effektiv för all indata, utom kanske liten datastorlek.

Asymptotisk komplexitetsuppskattning betecknas med den grekiska bokstaven Θ (theta).

f(n) = Θ(g(n)), om det finns c1, c2>0 och n0 så att c1*g(n)<=f(n)<=c2*g(n) , при n>n0.

Funktionen g(n) är en asymptotiskt korrekt uppskattning av algoritmens komplexitet - funktionen f(n), ovanstående olikhet kallas en asymptotisk likhet, och själva beteckningen Θ symboliserar uppsättningen funktioner som växer "lika snabbt" som funktionen g(n) - dvs. upp till multiplikation med en konstant. Som följer av ovanstående olikhet är skattningen Θ både en övre och en lägre uppskattning av komplexiteten. Det är inte alltid möjligt att få en uppskattning i denna form, så de övre och nedre uppskattningarna bestäms ibland separat.
Övre svårighetsgrad betecknas med den grekiska bokstaven Ο (omicron), och är en uppsättning funktioner som inte växer snabbare än g(n).
f(n)= Ο(g(n)), om det finns c>0 och n0 så att 0<=f(n)<=cg(n), при n>n0.
Lägre svårighetsgrad betecknas med den grekiska bokstaven Ω (omega), och är den uppsättning funktioner som inte växer långsammare än g(n).
f(n)= Ω(g(n)), om det finns c>0 och n0 så att 0<=cg(n)<=f(n), при n>n0.
Som en konsekvens: en asymptotisk uppskattning existerar endast om de nedre och övre gränserna för algoritmens komplexitet sammanfaller. I praktiken att analysera algoritmer förstås komplexitetsuppskattningen oftast som den övre uppskattningen av komplexitet. Detta är ganska logiskt, eftersom det viktigaste är att uppskatta den tid under vilken algoritmen garanterat kommer att slutföra sitt arbete, och inte den tid inom vilken den definitivt inte kommer att slutföras.

($APPTYPE KONSOL)

använder
SysUtils;
var n:heltal;
funktionsresultat(n:heltal):Heltal; //världens bildande
var i:Integer;
Börja
resultat:=0;
för i:= 2 till n div 2 do
om n mod i =0 då
resultat:=resultat+1;
slutet;

Börja
läs(n); // ditt namn
skriv(resultat(n));
readln;
readln;
slutet.
slutet.

4. Rekursion med memorering (en transparent version av dynamisk programmering). Ett exempel på snabb beräkning av binomialkoefficienter med formeln C(n,m)=C(n-1,m)+C(n-1,m-1)

Det finns ett sätt att lösa problemet med upprepade beräkningar. Det är uppenbart - du måste komma ihåg de hittade värdena för att inte beräkna dem igen varje gång. Naturligtvis kommer detta att kräva aktiv användning av minne. Till exempel kan en rekursiv algoritm för att beräkna Fibonacci-tal enkelt kompletteras med tre "linjer":

skapa en global array FD bestående av nollor;

efter att ha beräknat talet F(n), placera dess värde i FD[n];

i början av den rekursiva proceduren, kontrollera att FD[n] = 0 och i så fall returnera FD[n] som ett resultat, och fortsätt annars till den rekursiva beräkningen av F(n).

(Funktion i Pascal)

funktion C(m, n:Byte):Longint;

Om (m=0) eller (m=n)

Annars C:=C(m, n-1)+C(m-1, n-1)

(Procedur i Pascal)

Procedur C(m, n: Byte; Var R: Longint);

Var R1, R2: Longint;

Om (m=0) eller (m=n)

Algoritmanalys –

Typer av analyser

Värsta fall: T(n)

Genomsnittligt fall: T(n)

Asymptotisk uppskattning

f (n) = O(g(n)) Þ

($c > 0, n 0 >

O(g(n)) = (f(n): $c > 0, n 0 >

Exempel: 2n 2 = O(n 3)

Slå samman sortering

om (sid< r) //1

Rekursionsträd: T(n) = 2*T(n/2) +cn, med –const, c>0

Metodik för att utvärdera rekursiva algoritmer.

Iterationsmetod

Baserat på formeln T(n) skriver vi formeln för det mindre elementet som ligger till höger om formeln för T(n).

Ersätt den högra sidan av den resulterande formeln med den ursprungliga formeln

Vi utför de två första stegen tills vi expanderar formeln till en serie utan funktionen T(n)

Låt oss uppskatta den resulterande serien baserat på aritmetik eller geometrisk progression

T(n)=T(n-1)+n, T(l)=1

T(n)=θ(g(n)), g(n)=?

T(n-1)=T(n-2)+(n-1)

T(n-2)=T(n-3)+(n-2)

T(n-3)+(n-2)+(n-1)+n=…

1+…(n-2)+(n-1)+n=

Rekursionsträd - en grafisk metod för att visa ersättningen av en relation i sig själv

T(n)=2T(n/2)+n2

T(n/4) T(n/4) T(n/4) T(n/4)

(n/2) 2 (n/2) 2 log n (1/2)*n 2

(n/4) 2 (n/4) 2 (n/4) 2 (n/4) 2 (1/4)*n 2

Substitutionsmetod

Gissa (föreslå) en lösning
Kontrollera lösningen med induktion
Hitta och ersätt konstanter

T(n) = 2T(n/2) + n

T(n) = (n log n)

Induktionsförutsättning: T(n) ≤ с * n* log n, c>0

Låt denna uppskattning vara sann för n/2

T(n/2) ≤ c*(n/2)*log(n/2)

Låt oss ersätta den med den ursprungliga formeln för T(n)

T(n) ≤ 2*(c*(n/2)*log(n/2))+n ≤

c*n*log(n/2)+n =

c*n*log n - c*n*log 2 +n =

c*n*log n - c*n +n ≤

c*n*log n

c≥1, n ≥ 2

Huvudsats om återkommande uppskattningar

T (n) = aT (n/b) + f (n), a ≥ 1, b > 1, f (n) − (f (n) > 0, n > n0)

Algoritmer för sortering av arrayer i polynomtid

Sortering är processen att ordna om objekt för en given

aggregat i en viss ordning (ökande

eller minskar).

Syftet med sorteringen är vanligtvis att underlätta efterföljande

söka efter element i en sorterad uppsättning.

Enkel insättningssortering

void sort_by_insertion(nyckel a , int N)

för (i=1; i< N; i++)

för (j=i-1; (j>=0)&& (x< a[j]); j--)

a = a[j];

Analys av enkel infogningssort

Antal jämförelser:

C (N) = 1 + 2 + 3 + ... + N - 1 = (N * (N -1))/2= O (N 2)

Total tid: T(N) = θ(N 2)

Sortering genom enkelt byte. Bubbelmetod.

void bubble_sort (nyckel a, int N)

för (i=0; i

för (j=N-l; j>i; j--)

om (a > a[j]) (

x = a[j]; a[j] = a[j-1]; a[j-1] = x;

Sortering av analys genom enkelt utbyte

Värsta fall: omvänd ordnad array

Antal jämförelser:

C(N) = (N - 1) + (N - 2) + ... + 1 = (N * (N-1))/2 = O(N 2)

Total tid: T(N) = θ(N 2)

Tillägg

Nod* _Add(Nod *r, T s)

r = ny nod(er);

annat om (s< r->inf)

r->vänster = _Lägg till(r->vänster, s);

r->höger = _Lägg till(r->höger, s);

Ta bort ett element från trädet

Träd T med rot n och nyckel K.

ta bort från träd T en nod med nyckeln K (om det finns en).

Algoritm:

Om träd T är tomt, stoppa;

Jämför annars K med nyckeln X för rotnoden n.

Om K>X, ta bort K rekursivt från det högra underträdet av T;

Om K

Om K=X måste tre fall beaktas.

Om båda barnen inte finns, tar vi bort den aktuella noden och återställer referensen till den från föräldernoden;

Om ett av barnen saknas, lägger vi värdena för fälten för barn m istället för motsvarande värden för rotnoden, skriver över dess gamla värden och frigör minnet som upptas av noden m;

Om båda barnen är närvarande, så hittar vi noden m som ligger bredvid den givna;

kopiera data (förutom länkar till underordnade element) från m till n;

ta bort nod m rekursivt.

Element efter givet

Givet: träd T och nyckel x

Returnera en pekare till elementet bredvid x eller NULL om x är det sista elementet i trädet.

Algoritm:

Bedömer två fall separat.

Om det högra underträdet i en vertex x inte är tomt, är elementet bredvid x minimielementet i detta underträd.

Annars, om det högra underträdet av vertex x är tomt. Vi flyttar oss upp från x tills vi hittar en vertex som är det vänstra barnet till sin förälder. Denna förälder (om det finns en) kommer att vara det element som söks efter.

Infoga noder

Att infoga en ny nyckel i ett AVL-träd görs på samma sätt som det görs i enkla sökträd: vi går ner i trädet, väljer höger eller vänster rörelseriktning beroende på resultatet av att jämföra nyckeln i den aktuella noden och den isatta nyckeln.

Den enda skillnaden är att när man återvänder från rekursion (det vill säga efter att nyckeln har infogats i antingen höger eller vänster underträd), balanseras den aktuella noden om. Obalansen som uppstår vid en sådan insättning i någon nod längs rörelsebanan överstiger inte två, vilket betyder att tillämpningen av balanseringsfunktionen som beskrivs ovan är korrekt.

Ta bort noder

För att ta bort en vertex från ett AVL-träd tas algoritmen som bas, som vanligtvis används när man tar bort noder från ett standard binärt sökträd. Vi hittar nod p med den givna nyckeln k, i det högra underträdet hittar vi nod min med den minsta nyckeln och ersätter den borttagna noden p med den hittade noden min.

Under implementeringen uppstår flera alternativ. Först och främst, om den hittade noden p inte har ett höger underträd, så, enligt egenskapen hos AVL-trädet, kan denna nod till vänster bara ha en enda barnnod (träd med höjd 1), eller nod p är till och med ett löv. I båda dessa fall tar du helt enkelt bort nod p och returnerar som ett resultat en pekare till den vänstra barnnoden på p.

Låt nu p ha ett rätt underträd. Vi hittar miniminyckeln i detta underträd. Enligt egenskapen hos ett binärt sökträd är denna nyckel placerad i slutet av den vänstra grenen, med början från trädets rot. Vi använder den rekursiva findmin-funktionen.

removemin-funktion - tar bort minimielementet från ett givet träd. Enligt egenskapen hos ett AVL-träd har det minimala elementet till höger antingen en enda nod eller är tomt. I båda fallen behöver du bara returnera pekaren till den högra noden och utföra balansering på vägen tillbaka (när du kommer tillbaka från rekursion).

Hashtabeller, kedjemetod

Direktadressering används för små uppsättningar nycklar. Det krävs att definiera en dynamisk uppsättning, vars varje element har en nyckel från uppsättningen U = (0,1,..., m - 1), där m inte är för stor, inga två element har samma nycklar.

För att representera en dynamisk uppsättning används en array (direkt adresserad tabell), T, vars varje position eller cell motsvarar en nyckel från nyckelutrymmet U.

Cell k pekar på ett element i mängden med tangenten k. Om mängden inte innehåller ett element med nyckeln k, så är T[k] = NULL.

Nyckelsökning tar tid O(1)

Nackdelar med direkt adressering:

Om nyckelutrymmet U är stort, lagra en tabell T med storleken |U| opraktisk, om inte omöjlig, beroende på mängden tillgängligt minne och storleken på tangentutrymmet

Uppsättningen K av faktiskt lagrade nycklar kan vara liten jämfört med nyckelutrymmet U, i vilket fall minnet som allokerats till tabell T är till stor del bortkastat.

En hashfunktion är en funktion h som bestämmer platsen för elementen i mängden U i tabellen T.

Vid hashning lagras ett element med nyckel k i cell h(k), hashfunktionen h används för att beräkna cellen för en given nyckel k. Funktionen h mappar nyckelutrymmet U till cellerna i hashtabellen T [O..m - 1]:

h: U → (0,1,..., m-1).

värdet h(k) kallas hashvärdet för nyckeln k.

När uppsättningen K av nycklar som lagras i ordboken är mycket mindre än utrymmet för möjliga nycklar U, kräver en hashtabell betydligt mindre utrymme än en direkt adresserande tabell.

Syftet med en hashfunktion är att minska arbetsintervallet för arrayindex, och istället för |U| värden kan du klara dig med bara m värden.

Minneskraven kan reduceras till θ(|K|), medan söktiden för ett element i hashtabellen förblir lika med O(1) - detta är en gräns för den genomsnittliga söktiden, medan i fallet med en direkt- adresseringstabell denna gräns är giltig för värsta fall.

En kollision är en situation där två nycklar mappar till samma cell.

Till exempel, h(43) = h(89) = h(112) = k

Kedjemetod:

Idé: Lagra element i en uppsättning med samma hashvärde som en lista.

h(51) = h(49) = h(63) = i

Analys

I värsta fall: om hashfunktionen för alla element i uppsättningen ger samma värde. Åtkomsttiden är Θ(n), med |U | = n.

Genomsnittligt fall: för fallet där hashvärdena är enhetligt fördelade.

Varje nyckel kan vara lika sannolikt att hamna i vilken cell som helst i tabellen, oavsett var de andra nycklarna hamnar.

Låt en tabell T ges och n nycklar lagras i den.

Då är a = n/m det genomsnittliga antalet nycklar i tabellcellerna.

Tiden för att söka efter ett saknat element är Θ(1 + α).

Konstant tid för att beräkna hashfunktionsvärdet plus tid för att gå igenom listan till slutet, eftersom den genomsnittliga längden på listan är α, då blir resultatet Θ(1) + Θ(α) = Θ(1 + α)

Om antalet tabellceller är proportionellt mot antalet element som lagras i den, då är n = O(m) och därför α = n/m = O(m)/m = O(1), vilket betyder att söka efter ett element i hashtabellen kräver i genomsnitt tid Θ(1).

Operationer

Infoga ett element i en tabell

Borttagning

kräver också O(1) tid

Välja en hashfunktion

Nycklarna ska vara jämnt fördelade över alla celler

Distributionsmönstret för hashfunktionsnycklar bör inte korrelera med datamönstren. (Till exempel är uppgifterna jämna tal).

Metoder:

Indelningsmetod

Multiplikationsmetod

Indelningsmetod

h (k) = k mod m

Problem med liten divisor m

Exempel nr 1. m = 2 och alla nycklar är jämna Þ udda celler är det inte

fylld.

Exempel nr 2. m = 2 rÞ hash är inte beroende av bitar ovan r.

Multiplikationsmetod

Låta m= 2 r, nycklarna är w-bit-ord.

h(k) = (A k mod 2 w) >> (w - r), Var

A mod 2 = 1 ∩ 2 w-1< A< 2 w

Du ska inte välja A nära 2 w-1 Och 2w

Denna metod är snabbare än divisionsmetoden

Multiplikationsmetod: exempel

m = 8 = 23, w = 7

Öppna adressering: sök

Sökning är också sekventiell forskning

Framgång när meningen hittas

Misslyckande när du hittar en tom cell eller går igenom hela tabellen.

Forskningsstrategier

Linjär -

h(k, i) = (h'(k) + i) mod m

Denna strategi är lätt att implementera, men är föremål för problem

primär klustring associerad med skapandet av en lång sekvens

aktiviteten hos ockuperade celler, vilket ökar den genomsnittliga söktiden.

Kvadratisk

h(k, i) = (h′(k) + c 1 i+ c 2 i 2) mod m

där h′(k) är en vanlig hashfunktion

Dubbel hashning –

h(k,i) = (h 1 (k) + i h 2 (k)) mod m.

Dubbel hashing

Denna metod ger utmärkta resultat, men h 2 (k) måste vara coprime till m.

Detta kan uppnås:

använda m som potenser av två och få h 2 (k) att bara producera udda tal

m = 2 r иh 2 (k)– udda.

m- primtal, värden h 2 – positiva heltal mindre än m

För enkelt m kan installeras

h1(k)=k mod m

h2(k)=1+(k mod m’)

m' mindre än m (m' =m-1 eller m-2)

Öppna adressering: Insättningsexempel

Låt tabell A ges:

Dubbel hashing

h2(k)=1+(k mod 11)

Var kommer elementet att bäddas in?

Öppen adressanalys

Ytterligare antagande för enhetlig hashning: varje nyckel är lika sannolikt att få någon av m! permutationer av tabellutforskningssekvenser

oavsett andra nycklar.

Att hitta ett saknat element

Antal försök för framgångsrik sökning

Öppna adressering

A< 1 - const Þ O(1)

Hur beter han sig? A:

Tabell 50 % slutför Þ2-forskning

Tabellen är 90% komplett Þ 10 studier

Tabellen är 100% komplett Þ m studier

Principen om girigt val

De säger att det är tillämpligt på optimeringsproblemet principen om girigt val, om en sekvens av lokalt optimala val ger en globalt optimal lösning.

Vanligtvis följer ett bevis på optimalitet detta mönster:

Det är bevisat att det giriga valet i det första steget inte stänger vägen till den optimala lösningen: för varje lösning finns det en annan, i överensstämmelse med det giriga valet och inte värre än den första.

Det visas att det delproblem som uppstår efter det giriga valet i det första steget liknar det ursprungliga.

Argumentationen avslutas med induktion.

Optimal för deluppgifter

Problemet sägs ha fastigheten optimalitet för delproblem, om den optimala lösningen på ett problem innehåller optimala lösningar för alla dess delproblem.

Konstruktion av Huffman-koden

Alla meddelanden består av en sekvens av tecken från något alfabet. Ofta, för att spara minne och öka hastigheten på informationsöverföringen, uppstår uppgiften att komprimera information. I det här fallet används specialteckenkodningsmetoder. Dessa inkluderar Huffman-koder, som ger komprimering från 20 % till 90 % beroende på typ av information.

Huffman-algoritmen hittar optimala teckenkoder baserat på frekvensen av tecken som används i den komprimerade texten.

Huffmans algoritm är ett exempel på en girig algoritm.

Låt oss anta att i en fil med längden 100 000 tecken är teckenfrekvenserna kända:

Vi behöver konstruera en binär kod där varje tecken representeras som en ändlig sekvens av bitar som kallas ett kodord. När man använder en enhetlig kod, där alla kodord är lika långa, spenderas minst tre bitar per tecken och hela filen kommer att förbruka 300 000 bitar.

En ojämn kod kommer att vara mer ekonomisk om ofta förekommande tecken kodas med korta bitsekvenser och sällan förekommande tecken med långa sekvenser. Vid kodning kommer hela filen att kosta (45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)*1000 = 224000. Det vill säga ojämn kod ger ca 25% besparing.

Prefixkoder

Betrakta koder där, för var och en av två sekvenser av bitar som representerar olika tecken, ingen av dem är ett prefix till den andra. Sådana koder kallas prefixkoder.

Vid kodning ersätts varje tecken med sin egen kod. Till exempel ser strängen abc ut som 0101100. För en prefixkod är avkodningen unik och sker från vänster till höger.

Det första tecknet i en text som är kodad med en prefixkod bestäms unikt, eftersom dess kodord inte kan vara början på något annat tecken. Efter att ha identifierat denna symbol och kasserat dess kodord, upprepar vi processen för de återstående bitarna, och så vidare.

För att effektivt implementera avkodning måste du lagra information om koden i en bekväm form. En möjlighet är att representera koden som kod binärt träd, vars blad motsvarar de tecken som ska kodas. I det här fallet bestämmer vägen från roten till den kodade symbolen kodningssekvensen av bitar: att flytta längs trädet till vänster ger 0, och att flytta till höger ger 1.

De interna noderna indikerar summan av frekvenser för bladen i motsvarande underträd.

Optimal för den här filen Koden motsvarar alltid ett binärt träd där varje vertex som inte är ett löv har två barn. Den enhetliga koden är inte optimal, eftersom motsvarande träd har en vertex med en son.

Ett träd med den optimala prefixkoden för en fil som använder alla tecken från någon uppsättning C och bara de innehåller exakt | C | lämnar en för varje symbol och exakt | C | - 1 noder som inte är löv.

Genom att känna till trädet T som motsvarar prefixkoden är det lätt att hitta antalet bitar som krävs för att koda filen. För varje tecken c från alfabetet C, låt f[c] beteckna antalet förekomster i filen och dT(c) djupet på dess motsvarande blad och därför längden på sekvensen av bitar som kodar c. För att sedan koda filen behöver du:

Detta värde kallas kostnaden för trädet T. Det är nödvändigt att minimera detta värde.

Huffman föreslagit en girig algoritm som konstruerar en optimal prefixkod. Algoritmen konstruerar ett träd T som motsvarar den optimala koden från botten till toppen, med början från uppsättningen | C | löv och göra | C | - 1 sammanslagning.

För varje symbol anges dess frekvens f [c]. För att hitta två objekt att sammanfoga, används en prioritetskö Q, med frekvenser f som prioriteringar - de två objekten med de lägsta frekvenserna slås samman.

Som ett resultat av sammanslagningen erhålls ett nytt objekt (inre vertex), vars frekvens beräknas lika med beloppet frekvenser för två sammanslagna objekt. Denna vertex läggs till i kön.

Huffman ( C)

1. n ←│C│ │ C │- effekt C

2. Q ← C Q – prioriterad kö

3. för jag ← 1 till n-1

4. do z ← Create_Node() z – nod som består av fält f, vänster, höger

5. x ← vänster [z] ← Avkö(Q)

6. y ← höger [z] ← Avkö(Q)

7. f[z] ← f[x] + f[y]

8. Kö(Q,z)

9. återvända Avkö(Q) returnera trädroten

Kvalitet

Kön implementeras som en binär hög.

Du kan skapa en kö i O(n).

Algoritmen består av en loop som exekveras n-1 gånger.

Varje köoperation slutförs i O(log n).

Den totala körtiden är O(n log n).

Nätverkskonstruktionsproblem

Förekomstområden: kommunikation och vägnät.

Given: många nätverksnoder (värdar, städer).

Nödvändig: bygga ett nätverk med den minsta totala kantvikten (längd på nätverkskablar, längd på vägar).

Grafmodell: nätverksnoder är grafnoder, E = V 2, vi känner till vikterna för alla kanter.

Resultat: gratis träd.

Tillvägagångssätt för att söka efter MOD

Vi konstruerar träd A genom att lägga till en kant i taget, och före varje iteration är det aktuella trädet en delmängd av någon MOD.

Vid varje steg i algoritmen bestämmer vi en kant (u, v) som kan läggas till A utan att bryta mot denna egenskap. Vi kallar en sådan kant säker

GenericMST(G, w)

2 medan A inte är MOD

3 gör Hitta en kant (u, v) som är säker för A

4 A ← A U ((u, v))

____________________________________________________________________________

Klassificering av revben

1. Träd revben(trädkanter) är kanterna på grafen G. En kant (u, v) är en trädkant om vertex v är öppet när man undersöker denna kant.

2. Bakkanter(bakkanter) är kanterna (u,v) som förbinder vertex u med dess förfader v i djupet-första sökträdet. Cykelkanter som kan förekomma i riktade grafer betraktas som bakkanter.

3. Raka revben(framkanter) är kanter (u,v) som inte är trädkanter och förbinder vertex u med dess avkomling v i sökträdet djup-först.

4. Korsiga revben(tvärkanter) - alla andra kanter på grafen. De kan koppla samman hörn av samma djup-första sökträd när ingen vertex är en förfader till en annan, eller så kan de koppla hörn i olika träd.

DFS-algoritmen kan modifieras så att den klassificerar de kanter som påträffas under drift. Nyckelidén är att varje kant (u, v) kan klassificeras med hjälp av färgen på vertex v när den först undersöks (även om raka och tvärgående kanter inte särskiljs).

vit färg indikerar att detta är en trädkant.
Den grå färgen definierar bakkanten.
Svart indikerar en rak eller tvär kant.

Det första fallet följer direkt av definitionen av algoritmen.

Med tanke på det andra fallet, notera att grå hörn alltid bildar en linjär kedja av ättlingar som motsvarar stapeln av aktiva anrop till DFS_Visit-proceduren; antalet grå hörn är en större än djupet för den sista öppna hörn i sökträdet för djupet-första. Utforskningen startar alltid från den djupaste gråa vertexen, så att en kant som når en annan grå vertex når den ursprungliga vertexens förfader.

I det tredje fallet har vi att göra med de återstående kanterna som inte faller under det första eller andra fallet. Det kan visas att en kant (u, v) är rak om d [u]< d [v], и перекрестным, если d [u] >d[v]

___________________________________________________________________________

Topologisk sortering

I prioritetskolumn varje kant (u, v) betyder u föregår v

Topologisk sortering graf är konstruktionen av en sekvens a, där för alla a i och a j gäller följande: $(a i ,a j) Þ i< j.

Topologisk sortering av en orienterad acyklisk graf G = (V, E) är en linjär ordning av alla dess hörn så att om grafen G innehåller en kant (u,v) så är u i denna ordning placerad före v (om grafen är inte acyklisk, sådan sortering är inte möjlig). Topologisk sortering av en graf kan ses som att ordna dess hörn längs en horisontell linje så att alla kanter är riktade från vänster till höger.

Sorterad sekvens: C2, C6, C7, C1, C3, C4, C5, C8

för varje(u i V) färg[u] = vit; // initiera

L = ny länkad_lista; // L är en tom länkad lista

för varje (u i V)

if (färg[u] == vit) TopVisit(u);

retur L; // L ger slutlig order

TopVisit(u) ( // starta en sökning på u

färg[u] = grå; // markera att du besökt

för varje (v i Adj(u))

if (färg[v] == vit) TopVisit(v);

Lägg till u på framsidan av L; // när du avslutar lägger du till i listan

T (n) = Θ(V + E)

Förfaranden

Skapa - Ställ in (u)- skapa en uppsättning från en vertex u.

Hitta - Ange (u)- hitta den mängd som hörnet tillhör uåterkommer i vilken uppsättning det angivna elementet finns. I själva verket returnerar detta ett av elementen i uppsättningen (kallas representativ eller ledare). Denna representant väljs i varje uppsättning av själva datastrukturen (och kan ändras över tiden, nämligen efter samtal Union).

Om anropet Hitta - Set för några två element returnerade samma värde, betyder det att dessa element är i samma uppsättning, annars är de i olika uppsättningar.

Union (u,v)- kombinera uppsättningar som innehåller hörn u Och v

Vi kommer att lagra uppsättningar av element i formuläret träd: ett träd motsvarar en uppsättning. Trädets rot är representanten (ledaren) för uppsättningen.

När det är implementerat betyder det att vi skapar en array förälder, där vi för varje element lagrar en länk till dess förfader i trädet. För trädrötter kommer vi att anta att deras förfader är de själva (dvs. länkslingorna på denna plats).

För att skapa ett nytt element (operation Skapa - Ställ in), skapar vi helt enkelt ett träd med rötter i vertex v , och noterar att dess förfader är sig själv.

För att kombinera två uppsättningar (drift Union(a,b)), hittar vi först ledarna för den mängd där a är belägen och den mängd där b är belägen. Om ledarna sammanfaller gör vi ingenting - det betyder att uppsättningarna redan var förenade. Annars kan du helt enkelt ange att förfadern till vertex b är lika med f (eller vice versa) - och därmed sammanfoga ett träd med ett annat.

Slutligen, genomförandet av ledarsökningsoperationen ( Hitta - Set(v)) är enkelt: vi klättrar upp för förfäderna från vertex v tills vi når roten, d.v.s. medan hänvisningen till förfadern inte leder till sig själv. Det är bekvämare att implementera denna operation rekursivt.

Path compression heuristic

Denna heuristik är utformad för att påskynda saker och ting Hitta - Set() .

Det ligger i det faktum att när efter samtalet Hitta - Set(v) vi hittar den ledare vi söker sid set, kom då ihåg det vid spetsen v och alla toppar passerade längs vägen - det är denna ledare sid. Det enklaste sättet att göra detta är att omdirigera dem förälder till denna topp sid .

Alltså mängden förfäder förälder innebörden ändras något: nu är det så komprimerad ancestor array, dvs. för varje vertex kan inte den omedelbara förfadern lagras där, utan förfaderns förfader, förfadern till förfaderns förfader osv.

Å andra sidan är det klart att det är omöjligt att göra dessa pekpinnar förälder alltid pekade på ledaren: annars, när man utför en operation Union skulle behöva uppdatera ledarna På) element.

Alltså till arrayen förälder bör närma sig exakt som en samling förfäder, kanske delvis komprimerade.

Använda Path Compression Heuristic tillåter att uppnå logaritmisk asymptotik: per förfrågan i genomsnitt

Analys

Initiering – O(V)

Slingan körs V gånger och varje extraheringsMin operation körs in - O(logV) gånger, totalt O(V logV) gånger

For-loopen körs O(E) gånger, minskaKey tar O(logV) tid.

Total körtid - O(V log V +E logV)= O(E logV)

Kortaste vägen egenskap

Låta p = (v 1, v 2 ..... v k)- den kortaste vägen från vertex v 1 till vertex vk i en given vägd riktad graf G = (U.E) med viktfunktion w: E → R a p ij = (v i, v i+1 .....v j)- partiell väg av väg p som går från vertex v i till toppen v j för godtyckliga i och j (1 ≤ i< j ≤ k). Sedan p ij– den kortaste vägen från spetsen v i Till v i

Dijkstra(G, w, s) (

för varje (u i V) ( // initiering

d [u] = +oändlighet

färg [u] = vit

d[s] =0 // dist till källan är 0

Q = ny PriQueue(V) // sätt alla hörn i Q

while (Q.nonEmpty()) ( // tills alla hörn har bearbetats

u = Q.extractMin() // välj u närmast s

för varje (v i Adj[u]) (

if (d[u] + w(u,v)< d[v]) { // Relax(u,v)

d [v] = d [u] + w(u,v)

Q.decreaseKey(v, d[v])

färg [u] = svart

Svårighetsgrad

Bellman-Ford-algoritmen avslutas inom en viss tidsperiod O(V*E) eftersom initieringen i rad 1 tar O(V) tid, för var och en av |V| - 1 pass längs kanterna på rad 2-4 tar O(E)-tid och att utföra for-slingan på rad 5-7 tar O(E)-tid. .