De Vraag
Hoe vind je de tijd complexiteit van een algoritme?
Wat heb ik gedaan voordat ik een vraag stel op SO ?
Ik heb deze, deze en vele andere links doorgenomen
Maar nergens heb ik een duidelijke en recht-toe-recht-aan uitleg kunnen vinden over hoe je tijd complexiteit kunt berekenen.
Wat weet ik ervan??
Zeg voor een code zo simpel als de onderstaande:
char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time
Zeg voor een lus zoals hieronder:
for (int i = 0; i < N; i++) {
Console.Write('Hello World !');
}
int i=0; Dit wordt maar één keer uitgevoerd.
De tijd wordt eigenlijk berekend tot i=0
en niet de declaratie.
i < N; Dit wordt N+1 keer uitgevoerd
i++ ; Dit wordt N keer uitgevoerd
Dus het aantal bewerkingen dat nodig is voor deze lus zijn
{1+(N+1)+N} = 2N+2
Opmerking: Dit kan nog steeds fout zijn, want ik ben niet zeker van mijn begrip van het berekenen van de tijd complexiteit
Wat ik wil weten ?
Ok, dus deze kleine basis berekeningen denk ik te kennen, maar in de meeste gevallen heb ik de tijd complexiteit gezien als
O(N), O(n2), O(log n), O(n!).... en vele andere,
Kan iemand mij helpen te begrijpen hoe men de tijd complexiteit van een algoritme berekent? Ik ben er zeker van dat er veel nieuwelingen zoals ik zijn die dit willen weten.
Dit is een uitstekend artikel: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm
Het onderstaande antwoord is gekopieerd van hierboven (voor het geval de uitstekende link kapot gaat)
De meest gebruikte metriek voor het berekenen van tijdcomplexiteit is de Big O notatie. Dit verwijdert alle constante factoren zodat de looptijd kan worden geschat in relatie tot N als N oneindig nadert. In het algemeen kun je het als volgt zien:
statement;
Is constant. De looptijd van het statement verandert niet ten opzichte van N.
for ( i = 0; i < N; i++ )
statement;
Is lineair. De looptijd van de lus is recht evenredig met N. Als N verdubbelt, verdubbelt ook de looptijd.
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ )
statement;
}
Is kwadratisch. De looptijd van de twee lussen is evenredig met het kwadraat van N. Als N verdubbelt, neemt de looptijd toe met N * N.
while ( low <= high ) {
mid = ( low + high ) / 2;
if ( target < list[mid] )
high = mid - 1;
else if ( target > list[mid] )
low = mid + 1;
else break;
}
Is logaritmisch. De looptijd van het algoritme is evenredig met het aantal keren dat N gedeeld kan worden door 2. Dit komt omdat het algoritme bij elke iteratie het werkgebied in tweeën deelt.
void quicksort ( int list[], int left, int right )
{
int pivot = partition ( list, left, right );
quicksort ( list, left, pivot - 1 );
quicksort ( list, pivot + 1, right );
}
Is N * log ( N ). De looptijd bestaat uit N lussen (iteratief of recursief) die logaritmisch zijn, het algoritme is dus een combinatie van lineair en logaritmisch.
In het algemeen is iets doen met elk item in één dimensie lineair, iets doen met elk item in twee dimensies is kwadratisch, en het werkgebied in tweeën delen is logaritmisch. Er zijn nog andere Big O maten zoals kubiek, exponentieel en vierkantswortel, maar die komen lang niet zo vaak voor. Big O notatie wordt beschreven als O (
Merk op dat geen van deze rekening heeft gehouden met de beste, gemiddelde en slechtste maatregelen. Elk zou zijn eigen Big O notatie hebben. Merk ook op dat dit een ZEER simplistische uitleg is. Big O is de meest gebruikelijke, maar het is ook complexer dan ik heb laten zien. Er zijn ook andere notaties zoals grote omega, kleine o, en grote theta. Je zult ze waarschijnlijk niet tegenkomen buiten een cursus algoritme-analyse. ;)
Hoe vind je de tijd complexiteit van een algoritme
Je telt op hoeveel machine-instructies het zal uitvoeren als functie van de grootte van zijn invoer, en vereenvoudigt dan de uitdrukking tot de grootste (als N heel groot is) term en kan elke vereenvoudigende constante factor opnemen.
Bijvoorbeeld, laten we eens kijken hoe we 2N + 2
machine instructies vereenvoudigen om dit te beschrijven als slechts O(N)
.
Waarom verwijderen we de twee `2``s??
We zijn geïnteresseerd in de prestaties van het algoritme als N groot wordt.
Beschouw de twee termen 2N en 2.
Wat is de relatieve invloed van deze twee termen als N groot wordt? Stel dat N een miljoen is.
Dan is de eerste term 2 miljoen en de tweede term slechts 2.
Daarom laten we alle termen behalve de grootste vallen voor grote N.
We zijn nu dus van 2N + 2
naar 2N
gegaan.
Traditioneel zijn we alleen geïnteresseerd in prestaties tot constante factoren.
Dit betekent dat het ons niet echt kan schelen of er een constant veelvoud van verschil in prestatie is als N groot is. De eenheid van 2N is in de eerste plaats toch al niet goed gedefinieerd. We kunnen dus vermenigvuldigen of delen met een constante factor om tot de eenvoudigste uitdrukking te komen.
Dus 2N
wordt gewoon N
.
O(n) is de grote O-notatie die gebruikt wordt om de tijdcomplexiteit van een algoritme te schrijven. Als je het aantal uitvoeringen in een algoritme optelt, krijg je een uitdrukking als 2N+2, in deze uitdrukking is N de dominante term (de term die het grootste effect op de uitdrukking heeft als zijn waarde stijgt of daalt). Nu is O(N) de tijd comlexiteit terwijl N de dominante term is. Voorbeeld
For i= 1 to n;
j= 0;
while(j<=n);
j=j+1;
hier is het totaal aantal executies voor de binnenste lus n+1 en het totaal aantal executies voor de buitenste lus n(n+1)/2, dus het totaal aantal executies voor het hele algoritme is n+1+n(n+1/2) = (n^2+3n)/2. hier is n^2 de dominante term dus de tijd complexiteit voor dit algoritme is O(n^2)