Print (i, J)
J +=1
i +=1
`` `
Dette involverer en indlejret 'mens' loop, hvor begge løkker itererer `n 'gange. Det samlede antal iterationer er `n * n =n^2`.
5. Anden polynomisk tid (O (n^k))
* Generaliseringer af det kvadratiske eksempel ovenfor. For eksempel ville tre indlejrede løkker, som hver iterere `n 'gange ville resultere i O (n^3) kompleksitet.
6. Eksponentiel tid (O (2^n)) eller værre
* Loopens udførelsestid vokser eksponentielt med inputstørrelsen. Dette indikerer ofte en dårligt designet algoritme eller et problem, der i sig selv er meget vanskeligt. Eksempler kan involvere at prøve alle mulige kombinationer af elementer.
Nøgleovervejelser:
* inputstørrelse (n): Hvad repræsenterer `n`? Størrelsen på en matrix, størrelsen af et tal osv. Dette er kritisk for at udtrykke kompleksiteten med hensyn til input.
* Tilstandsvariabel ændringer: Hvordan ændres variablen (e), der kontrollerer loop -tilstanden i løkken? Stiger det med et konstant beløb, falder med en faktor osv.?
* operationer inde i løkken: Runtime for operationerne * inde * Loop betyder noget. Hvis du for eksempel har en O (n) operation inde i en løkke, der kører n gange, er den samlede kompleksitet O (n * n) =o (n^2).
hvordan man bestemmer runtime -kompleksitet:
1. Identificer inputstørrelsen (n): Hvad er den relevante størrelsesparameter?
2. Bestem antallet af iterationer: Hvor mange gange udføres loopen *i forhold til `n` *? Dette er den centrale del.
3. Overvej operationer inde i løkken: Hvis løkken indeholder komplekse operationer, skal deres runtime -kompleksitet tages i betragtning. Den samlede kompleksitet bliver kompleksiteten af loop -iterationer, der er ganget med kompleksiteten af den dyreste operation i løkken.
4. udtrykke kompleksiteten: Brug stor O -notation (O (), ω (), θ ()) til at repræsentere den øvre grænse, nedre grænse eller stram grænse af runtime. Typisk fokuserer vi på Big O (worst-case-scenario).
Eksempel:
`` `Python
def process_array (arr):
n =len (arr)
i =0
Mens jeg
j =i + 1
mens j
Hvis arr [i]> arr [j]:
arr [i], arr [j] =arr [j], arr [i] # konstant tidsskift
J +=1
i +=1
Return arr
`` `
Analyse:
* `n` er længden af input -arrayet` arr`.
* Den ydre sløjfe (`Jeg ') kører` n' gange.
* Den indre sløjfe (`j`) kører cirka` n - i 'gange. I værste tilfælde, når `jeg er 0, kører det` n 'gange.
* Swap -operationen inde i den indre sløjfe er O (1).
Derfor bidrager de indlejrede løkker til O (n^2) kompleksitet. Swap er konstant tid og påvirker ikke den samlede o (n^2) runtime. Denne algoritme ligner udvælgelsessortering.
Sammenfattende skal du omhyggeligt analysere, hvor mange gange sløjfen udføres i forhold til inputstørrelsen og overveje kompleksiteten af de operationer, der udføres i løkken for at bestemme runtime -kompleksiteten af en 'mens' loop.
