tryck (i, j)
J +=1
I +=1
`` `
Detta innebär en kapslad "medan" slinga, där båda slingorna itererar "n" -tider. Det totala antalet iterationer är `n * n =n^2`.
5. Annan polynomtid (O (n^k))
* Generaliseringar av det kvadratiska exemplet ovan. Till exempel skulle tre kapslade slingor som varje `n` -tider skulle resultera i o (n^3) komplexitet.
6. Exponentiell tid (o (2^n)) eller sämre
* Loopens körningstid växer exponentiellt med ingångsstorleken. Detta indikerar ofta en dåligt utformad algoritm eller ett problem som i sig är mycket svårt. Exempel kan innebära att du försöker alla möjliga kombinationer av element.
Nyckelöverväganden:
* Ingångsstorlek (n): Vad representerar `n`? Storleken på en matris, storleken på ett nummer osv. Detta är avgörande för att uttrycka komplexiteten när det gäller inmatning.
* Skick Variabla ändringar: Hur förändras variabeln (er) som kontrollerar slingtillståndet i slingan? Ökar det med en konstant mängd, minskning med en faktor etc.?
* operationer inuti slingan: Runtime för operationerna * inuti * slingan är viktig. Om du till exempel har en O (n) -operation inuti en slinga som går n gånger, är den övergripande komplexiteten o (n * n) =o (n^2).
Hur man bestämmer runtime -komplexitet:
1. Identifiera ingångsstorleken (n): Vad är den relevanta storleksparametern?
2. Bestäm antalet iterationer: Hur många gånger körs slingan *i förhållande till `n` *? Detta är kärndelen.
3. Överväg operationer i slingan: Om slingan innehåller komplexa operationer måste deras runtime -komplexitet tas med i. Den övergripande komplexiteten blir komplexiteten i sling -iterationerna multiplicerade med komplexiteten i den dyraste operationen i slingan.
4. Uttryck komplexiteten: Använd stor o -notation (o (), ω (), θ ()) för att representera den övre gränsen, nedre gränsen eller snäva gränsen för runtime. Vanligtvis fokuserar vi på Big O (Worst-Case Scenario).
Exempel:
`` `python
DEF Process_Array (ARR):
n =len (arr)
i =0
Medan jag
j =i + 1
Medan j
Om arr [i]> arr [j]:
arr [i], arr [j] =arr [j], arr [i] # konstant tidsbyte
J +=1
I +=1
returnera
`` `
Analys:
* `n` är längden på ingångsgruppen` arr`.
* Den yttre slingan (`i ') körs` n` gånger.
* Den inre slingan (`j`) går ungefär` n - jag '. I värsta fall, när "jag" är 0, kör det "n" -tider.
* Swap -operationen inuti den inre slingan är O (1).
Därför bidrar de kapslade slingorna till O (n^2) komplexitet. Bytet är konstant tid och påverkar inte den totala o (n^2) runtime. Denna algoritm liknar urvalssortering.
Sammanfattningsvis, för att bestämma runtime -komplexiteten för en "medan" slinga, analysera försiktigt hur många gånger slingan kör relativt inmatningsstorleken och överväga komplexiteten i de operationer som utförs i slingan.
