Hoe de tijdcomplexiteit van een algoritme te vinden

De Vraag

Hoe de tijdcomplexiteit van een algoritme te vinden?

Wat heb ik gedaan voordat ik een vraag op SO plaatste?

Ik heb dit, dezeen vele andere links

Maar nergens kon ik een duidelijke en ongecompliceerde uitleg vinden voor het berekenen van tijdcomplexiteit.

Wat weet ik?

Zeg voor een code die zo simpel is 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 slechts eenmaaluitgevoerd.
De tijd wordt feitelijk berekend tot i=0en niet de aangifte.

ik < N;Dit wordt N+1keer uitgevoerd

i++ ;Dit wordt Nkeer uitgevoerd

Dus het aantal bewerkingen dat nodig is voor deze lus is

{1+(N+1)+N} = 2N+2

Opmerking: dit kan nog steeds verkeerd zijn, omdat ik niet zeker ben van mijn begrip van het berekenen van tijdcomplexiteit

Wat ik wil weten?

Ok, dus deze kleine basisberekeningen denk ik te weten, maar in de meeste gevallen heb ik de tijdscomplexiteit gezien als

O(N), O(n2), O(log n), O(n!)…. en vele overig,

Kan iemand me helpen begrijpen hoe je de tijdcomplexiteit van een algoritme berekent? Ik weet zeker dat er genoeg nieuwelingen zoals ik zijn die dit willen weten.

Antwoord 1, autoriteit 100%

Hoe de tijdscomplexiteit van een algoritme te vinden

Je telt op hoeveel machine-instructies het zal uitvoeren als functie van de grootte van de invoer, en vereenvoudigt vervolgens de uitdrukking tot de grootste (wanneer N erg groot is) term en kan elke vereenvoudigende constante factor bevatten.

>

Laten we bijvoorbeeld eens kijken hoe we 2N + 2machine-instructies vereenvoudigen om dit te beschrijven als gewoon O(N).

Waarom verwijderen we de twee 2en ?

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 termijn 2 miljoen en de tweede termijn slechts 2.

Om deze reden laten we alle termen, behalve de grootste, vallen voor grote N.

Dus nu zijn we van 2N + 2naar 2Ngegaan.

Traditioneel zijn we alleen geïnteresseerd in prestaties tot constante factoren.

Dit betekent dat het ons niet uitmaakt of er een constant veelvoud van verschil in prestatie is wanneer N groot is. De eenheid van 2N is sowieso niet goed gedefinieerd. We kunnen dus vermenigvuldigen of delen door een constante factor om de eenvoudigste uitdrukking te krijgen.

Dus 2Nwordt gewoon N.

Antwoord 2, autoriteit 98%

Dit is een uitstekend artikel:
http://www.daniweb.com /software-ontwikkeling/computerwetenschappen/threads/13488/time-complexity-of-algorithm

Het onderstaande antwoord is van bovenaf gekopieerd (voor het geval de uitstekende link kapot gaat)

De meest gebruikte maatstaf voor het berekenen van tijdcomplexiteit is de Big O-notatie. Hierdoor worden alle constante factoren verwijderd, zodat de looptijd kan worden geschat in relatie tot N wanneer N oneindig nadert. Over het algemeen kun je het zo zien:

statement;

Is constant. De looptijd van de verklaring 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. Wanneer N verdubbelt, neemt ook de looptijd toe.

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. Wanneer 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 door 2 kan worden gedeeld. Dit komt doordat het algoritme het werkgebied bij elke iteratie 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, dus het algoritme is een combinatie van lineair en logaritmisch.

Over 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 andere Big O-maten, zoals kubieke, exponentiële en vierkantswortel, maar ze komen lang niet zo vaak voor. Big O-notatie wordt beschreven als O ( <type> )waarbij <type>de maat is. Het quicksort-algoritme zou worden beschreven als O ( N * log ( N ) ).

Houd er rekening mee dat bij dit alles geen rekening is gehouden met de beste, gemiddelde en slechtste gevallen. Elk zou zijn eigen Big O-notatie hebben. Merk ook op dat dit een ZEER simplistische uitleg is. Big O is de meest voorkomende, 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 algoritmeanalyse. 😉

Antwoord 3, autoriteit 44%

Vanaf hier genomen – Inleiding tot de tijdscomplexiteit van een algoritme

1. Inleiding

In de informatica kwantificeert de tijdcomplexiteit van een algoritme de hoeveelheid tijd die een algoritme nodig heeft om te worden uitgevoerd als een functie van de lengte van de tekenreeks die de invoer vertegenwoordigt.

2. Grote O-notatie

De tijdscomplexiteit van een algoritme wordt gewoonlijk uitgedrukt met de grote O-notatie, die coëfficiënten en termen van lagere orde uitsluit. Op deze manier uitgedrukt, wordt gezegd dat de tijdcomplexiteit asymptotisch wordt beschreven, d.w.z. naarmate de invoergrootte oneindig wordt.

Als bijvoorbeeld de tijd die een algoritme nodig heeft voor alle invoer met de grootte n maximaal 5n³+ 3n is, is de asymptotische tijdcomplexiteit O(n³). Daarover later meer.

Nog enkele voorbeelden:

• 1 = O(n)
• n = O(n²)
• log(n) = O(n)
• 2 n + 1 = O(n)

3. O(1) Constante tijd:

Er wordt gezegd dat een algoritme in constante tijd draait als het dezelfde hoeveelheid tijd nodig heeft, ongeacht de invoergrootte.

Voorbeelden:

• array: toegang tot elk element
• stapel met vaste grootte: push- en pop-methoden
• wachtrij met vaste grootte: methoden voor in de wachtrij plaatsen en uit de wachtrij halen

4. O(n) Lineaire tijd

Er wordt gezegd dat een algoritme in lineaire tijd werkt als de uitvoering ervan recht evenredig is met de invoergrootte, d.w.z. de tijd groeit lineair naarmate de invoer groter wordt.

Beschouw de volgende voorbeelden, hieronder zoek ik lineair naar een element, dit heeft een tijdcomplexiteit van O(n).

int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
    if(find == numbers[i])
    {
        return;
    }
}

Meer voorbeelden:

• Array: lineair zoeken, doorlopen, minimum zoeken, enz.
• ArrayList: bevat methode
• Wachtrij: bevat methode

5. O(log n) Logaritmische tijd:

Er wordt gezegd dat een algoritme in logaritmische tijd wordt uitgevoerd als de uitvoering ervan evenredig is met de logaritme van de invoergrootte.

Voorbeeld: Binair zoeken

Herinner je het spel “twintig vragen” – de taak is om de waarde van een verborgen getal in een interval te raden. Elke keer dat u een gok doet, wordt u verteld of uw gok te hoog of te laag is. Het spel met twintig vragen impliceert een strategie die uw gokgetal gebruikt om de intervalgrootte te halveren. Dit is een voorbeeld van de algemene methode voor het oplossen van problemen die bekend staat als binair zoeken

6. O(n²) Kwadratische tijd

Er wordt gezegd dat een algoritme in kwadratische tijd wordt uitgevoerd als de uitvoering ervan evenredig is met het kwadraat van de invoergrootte.

Voorbeelden:

• Bubble Sorteren
• Selectie sorteren
• Invoegsortering

7. Enkele nuttige links

• Big-O Misvattingen
• Bepalen De complexiteit van het algoritme
• Big O-spiekbriefje

Antwoord 4, autoriteit 26%

Hoewel er enkele goede antwoorden op deze vraag zijn. Ik zou hier nog een antwoord willen geven met verschillende voorbeelden van loop.

• O(n): Tijdcomplexiteit van een lus wordt beschouwd als O(n)als de lusvariabelen met een constante hoeveelheid worden verhoogd/verlaagd. De volgende functies hebben bijvoorbeeld O(n)tijdcomplexiteit.

  // Here c is a positive integer constant   
  for (int i = 1; i <= n; i += c) {  
      // some O(1) expressions
  }
  for (int i = n; i > 0; i -= c) {
      // some O(1) expressions
  }
  

• O(n^c): De tijdcomplexiteit van geneste lussen is gelijk aan het aantal keren dat de binnenste instructie wordt uitgevoerd. De volgende voorbeeldlussen hebben bijvoorbeeld O(n^2)tijdcomplexiteit

  for (int i = 1; i <=n; i += c) {
     for (int j = 1; j <=n; j += c) {
        // some O(1) expressions
     }
  }
  for (int i = n; i > 0; i += c) {
     for (int j = i+1; j <=n; j += c) {
        // some O(1) expressions
  }
  

  Selectiesortering en invoegsortering hebben bijvoorbeeld O(n^2)tijdcomplexiteit.

• O(Logn)Tijdscomplexiteit van een lus wordt beschouwd als O(Logn)als de lusvariabelen worden gedeeld/vermenigvuldigd met een constant bedrag.

  for (int i = 1; i <=n; i *= c) {
     // some O(1) expressions
  }
  for (int i = n; i > 0; i /= c) {
     // some O(1) expressions
  }
  

  Binnenair zoeken heeft bijvoorbeeld O(Logn)tijdcomplexiteit.

• O(LogLogn)Tijdscomplexiteit van een lus wordt beschouwd als O(LogLogn)als de lusvariabelen exponentieel worden verminderd/verhoogd met een constante hoeveelheid.

  // Here c is a constant greater than 1   
  for (int i = 2; i <=n; i = pow(i, c)) { 
     // some O(1) expressions
  }
  //Here fun is sqrt or cuberoot or any other constant root
  for (int i = n; i > 0; i = fun(i)) { 
     // some O(1) expressions
  }
  

Een voorbeeld van tijdcomplexiteitsanalyse

int fun(int n)
{    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j += i)
        {
            // Some O(1) task
        }
    }    
}

Analyse:


For i = 1, the inner loop is executed n times.
For i = 2, the inner loop is executed approximately n/2 times.
For i = 3, the inner loop is executed approximately n/3 times.
For i = 4, the inner loop is executed approximately n/4 times.
…………………………………………………….
For i = n, the inner loop is executed approximately n/n times.


Dus de totale tijdscomplexiteit van het bovenstaande algoritme is (n + n/2 + n/3 + … + n/n), wat n * (1/1 + 1/2 + 1/3 + … + 1/n)

Het belangrijkste van reeksen (1/1 + 1/2 + 1/3 + … + 1/n)is gelijk aan O(Logn). Dus de tijdscomplexiteit van de bovenstaande code is O(nLogn).

Referentie:
1
2
3

Antwoord 5, autoriteit 17%

Tijdcomplexiteit met voorbeelden

1 – Basisbewerkingen (rekenkunde, vergelijkingen, toegang tot array-elementen, toewijzing): de looptijd is altijd constant O(1)

Voorbeeld:

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1.000.000.000.000.000.000         // O(1)

2 – If then else statement: alleen de maximale looptijd nemen van twee of meer mogelijke statements.

Voorbeeld:

age = read(x)                               // (1+1) = 2
if age < 17 then begin                      // 1
      status = "Not allowed!";              // 1
end else begin
      status = "Welcome! Please come in";   // 1
      visitors = visitors + 1;              // 1+1 = 2
end;

De complexiteit van de bovenstaande pseudocode is dus T(n) = 2 + 1 + max(1, 1+2) = 6. De grote oh is dus nog steeds constant T(n) = O(1) .

3 – Looping (for, while, repeat): De looptijd voor deze instructie is het aantal looping vermenigvuldigd met het aantal bewerkingen binnen die looping.

Voorbeeld:

total = 0;                                  // 1
for i = 1 to n do begin                     // (1+1)*n = 2n
      total = total + i;                    // (1+1)*n = 2n
end;
writeln(total);                             // 1

De complexiteit is dus T(n) = 1+4n+1 = 4n + 2. Dus, T(n) = O(n).

4 – Geneste lus (looping binnen looping): aangezien er ten minste één looping binnen de hoofdlooping is, werd bij de looptijd van deze instructie O(n^2) of O(n^3) gebruikt.

Voorbeeld:

for i = 1 to n do begin                     // (1+1)*n  = 2n
   for j = 1 to n do begin                  // (1+1)n*n = 2n^2
       x = x + 1;                           // (1+1)n*n = 2n^2
       print(x);                            // (n*n)    = n^2
   end;
end;

Gemeenschappelijke looptijd

Er zijn enkele veelvoorkomende looptijden bij het analyseren van een algoritme:

1. O(1) – Constante tijd
   Constante tijd betekent dat de looptijd constant is en niet wordt beïnvloed door de invoergrootte.

2. O(n) – Lineaire tijd
   Wanneer een algoritme n invoergrootte accepteert, zou het ook n bewerkingen uitvoeren.

3. O(log n) – Logaritmische tijd
   Algoritme met looptijd O(log n) is iets sneller dan O(n). Gewoonlijk verdeelt het algoritme het probleem in subproblemen van dezelfde grootte. Voorbeeld: binair zoekalgoritme, binair conversiealgoritme.

4. O(n log n) – Linearitmische tijd
   Deze looptijd wordt vaak gevonden in “verdeel & heers algoritmen” die het probleem recursief in subproblemen verdelen en deze vervolgens in n tijd samenvoegen. Voorbeeld: Sorteeralgoritme samenvoegen.

5. O(n²) – Kwadratische tijd
   Kijk Bubble Sort-algoritme!

6. O(n³) – Kubieke tijd
   Het heeft hetzelfde principe met O(n²).

7. O(2ⁿ) – Exponentiële tijd
   Het is erg traag naarmate de invoer groter wordt, als n = 1000.000, zou T(n) 21.000.000 zijn. Brute Force-algoritme heeft deze looptijd.

8. O(n!) – Faculteit Tijd
   DE LANGZAAMSTE !!! Voorbeeld: Travel Salesman Problem (TSP)

Genomen uit dit artikel. Zeer goed uitgelegd zou het moeten lezen.

Antwoord 6, autoriteit 9%

Als je code analyseert, moet je het regel voor regel analyseren, elke bewerking tellend/tijdscomplexiteit herkennen, uiteindelijk moet je het optellen om een volledig beeld te krijgen.

U kunt bijvoorbeeld één eenvoudige lus hebben met lineaire complexiteit, maar later in datzelfde programma kunt u een drievoudige lus hebben met kubieke complexiteit, dus uw programma zal kubieke complexiteithebben. Functievolgorde van groei komt hier in het spel.

Laten we eens kijken wat de mogelijkheden zijn voor tijdcomplexiteit van een algoritme, je kunt de volgorde van groei zien die ik hierboven noemde:

• Constante tijdheeft een groeivolgorde 1, bijvoorbeeld: a = b + c.

• Logaritmische tijdheeft een groeivolgorde LogN, dit komt meestal voor
  wanneer u iets in tweeën deelt (binair zoeken, bomen, zelfs lussen), of iets op dezelfde manier vermenigvuldigt.

• Lineair, volgorde van groei is bijvoorbeeld N

  int p = 0;
  for (int i = 1; i < N; i++)
    p = p + 2;
  

• Linearitmisch, volgorde van groei is n*logN, komt meestal voor in verdeel-en-heers-algoritmen.

• Kubiek, volgorde van groei N^3, klassiek voorbeeld is een drievoudige lus waarbij je alle drietallen aanvinkt:

  int x = 0;
  for (int i = 0; i < N; i++)
     for (int j = 0; j < N; j++)
        for (int k = 0; k < N; k++)
            x = x + 2
  

• Exponentieel, volgorde van groei 2^N, komt meestal voor wanneer u uitgebreid zoekt, bijvoorbeeld subsets van sommige ingesteld.

Antwoord 7, autoriteit 9%

Los gezegd is tijdcomplexiteit een manier om samen te vatten hoe het aantal bewerkingen of runtime van een algoritme groeit naarmate de invoer groter wordt.

Zoals de meeste dingen in het leven, kan een cocktailparty ons helpen het te begrijpen.

O(N)

Als je op het feest aankomt, moet je iedereen de hand schudden (doe een bewerking op elk item). Naarmate het aantal aanwezigen Ntoeneemt, neemt de tijd/het werk dat nodig is om iedereen de hand te schudden toe naarmate O(N).

Waarom O(N)en niet cN?

Er is variatie in de hoeveelheid tijd die nodig is om mensen de hand te schudden. Je zou dit kunnen uitmiddelen en vastleggen in een constante c. Maar de fundamentele operatie hier — iedereen de hand schudden — zou altijd evenredig zijn aan O(N), wat cook was. Als we twijfelen of we naar een cocktailparty moeten, zijn we vaak meer geïnteresseerd in het feit dat we iedereen moeten ontmoeten dan in de minutieuze details van hoe die vergaderingen eruitzien.

O(N^2)

De gastheer van de cocktailparty wil dat je een gek spel speelt waarbij iedereen elkaar ontmoet. Daarom moet je N-1andere mensen ontmoeten en, omdat de volgende persoon jou al heeft ontmoet, moeten ze N-2mensen ontmoeten, enzovoort. De som van deze reeks is x^2/2+x/2. Naarmate het aantal aanwezigen groeit, wordt de term x^2snelgroot, dus laten we al het andere achterwege.

O(N^3)

Je moet iedereen ontmoeten en tijdens elke vergadering moet je over iedereen in de kamer praten.

O(1)

De host wil iets aankondigen. Ze klappen in een wijnglas en spreken luid. Iedereen hoort ze. Het blijkt dat het niet uitmaakt hoeveel aanwezigen er zijn, deze operatie kost altijd evenveel tijd.

O(log N)

De gastheer heeft iedereen in alfabetische volgorde aan tafel gezet. Waar is Daan? Je redeneert dat hij ergens tussen Adam en Mandy moet zijn (zeker niet tussen Mandy en Zach!). Staat hij daarom tussen George en Mandy? Nee. Hij moet tussen Adam en Fred zijn, en tussen Cindy en Fred. En zo verder… we kunnen Dan efficiënt lokaliseren door naar de helft van de set te kijken en dan naar de helft van die set. Uiteindelijk kijken we naar O(log_2 N)individuen.

O(N log N)

Je zou kunnen vinden waar je aan tafel kunt gaan zitten met behulp van het bovenstaande algoritme. Als een groot aantal mensen één voor één naar de tafel zou komen en dit allemaal zouden doen, zou dat O(N log N)tijd kosten. Dit blijkt te zijn hoe lang het duurt om een verzameling items te sorteren wanneer ze moeten worden vergeleken.

Beste/slechtste geval

Je komt aan op het feest en moet Inigo vinden – hoe lang duurt het? Het hangt af van wanneer je aankomt. Als iedereen aan het rondscharrelen is, heb je het ergste bereikt: het zal O(N)tijd kosten. Als iedereen echter aan tafel zit, duurt het slechts O(log N)tijd. Of misschien kun je gebruik maken van de wijnglas-schreeuwende kracht van de gastheer en het kost slechts O(1)tijd.

Ervan uitgaande dat de host niet beschikbaar is, kunnen we zeggen dat het Inigo-finding-algoritme een ondergrens heeft van O(log N)en een bovengrens van O(N), afhankelijk van de staat van het feest wanneer je aankomt.

Ruimte & Communicatie

Dezelfde ideeën kunnen worden toegepast om te begrijpen hoe algoritmen ruimte of communicatie gebruiken.

Knuth heeft een mooi artikel over de eerste geschreven, getiteld “The Complexity of Songs”.

Theorema 2: Er bestaan willekeurig lange liederen van complexiteit O(1).

BEWIJS: (vanwege Casey en de Sunshine Band). Beschouw de nummers Sk gedefinieerd door (15), maar met

V_k = 'That's the way,' U 'I like it, ' U
U   = 'uh huh,' 'uh huh'

voor alle k.

Antwoord 8

Ik weet dat deze vraag een heel eind teruggaat en er zijn hier enkele uitstekende antwoorden, maar ik wilde nog iets delen voor de wiskundig ingestelde mensen die in dit bericht zullen struikelen. De Hoofdstellingis een ander handig ding om te weten bij het bestuderen van complexiteit. Ik zag het niet vermeld in de andere antwoorden.

Antwoord 9

O(n) is de grote O-notatie die wordt gebruikt voor het schrijven van de tijdcomplexiteit van een algoritme. Als je het aantal uitvoeringen in een algoritme bij elkaar optelt, krijg je een uitdrukking in resultaat zoals 2N+2, in deze uitdrukking is N de overheersende term (de term heeft het grootste effect op de uitdrukking als de waarde ervan toeneemt of afneemt). Nu is O(N) de tijdscomplexiteit terwijl N de term domineert.
Voorbeeld

For i= 1 to n;
  j= 0;
while(j<=n);
  j=j+1;

hier is het totale aantal uitvoeringen voor de binnenste lus n+1 en het totale aantal uitvoeringen voor de buitenste lus is n(n+1)/2, dus het totale aantal uitvoeringen voor het hele algoritme is n+1+n(n+ 1/2) = (n^2+3n)/2.
hier is n^2 de overheersende term, dus de tijdscomplexiteit voor dit algoritme is O(n^2)