Att bestämma effektiviteten hos en algoritm innebär att analysera dess
tidskomplexitet och
rymdkomplexitet . Detta hjälper oss att förstå hur algoritmens resursanvändning (tid och minne) skalar med storleken på ingången. Här är en uppdelning av datorproceduren:
1. Förstå tidskomplexitet och rymdkomplexitet:
* Tidskomplexitet: Mäter hur mycket tid en algoritm tar för att slutföra som en funktion av ingångsstorleken (ofta betecknad som 'n'). Vi är intresserade av * hur * exekveringstiden växer, inte den exakta tiden på några sekunder.
* Rymdkomplexitet: Mäter mängden minne (eller utrymme) som en algoritm kräver som en funktion av ingångsstorleken 'n'. Detta inkluderar utrymmet för inmatningsdata och eventuella hjälpdatastrukturer som används av algoritmen.
2. Identifiera nyckeloperationer:
* grundläggande operationer: Identifiera de operationer som bidrar väsentligt till exekveringstiden. Dessa kan inkludera:
* Aritmetiska operationer (+, -, \*, /, %)
* Jämförelser (<,>, ==,! =)
* Uppdrag (=)
* Array Accesses (arr [i])
* Minnesallokeringar och återförsäljningar (beroende på språket)
* Fokusera på dominerande operationer: Vissa operationer kommer att genomföras mycket oftare än andra. Fokusera på dessa * dominerande * operationer, eftersom de kommer att ha den största inverkan på den totala körtiden. I en sorteringsalgoritm är till exempel jämförelser och swappar dominerande.
3. Analysera algoritmens struktur (kod genomgång):
* sekventiella uttalanden: Uttalanden som utförs i följd bidrar med en konstant tid eller utrymme.
* slingor: Tidskomplexiteten för en slinga beror på hur många gånger det iterates:
* enkel slinga (linjär): `` för i inom räckvidd (n):... `kör 'n' gånger, så komplexiteten är o (n).
* kapslade slingor (kvadratiska, kubiska, etc.): `för i inom räckvidd (n):för j inom intervallet (n):...` exekverar 'n * n' gånger, så komplexiteten är o (n^2).
* slinga med logaritmiskt beteende: `Medan n> 1:n =n // 2` kör log2 (n) gånger, så komplexiteten är o (log n).
* slinga med beroende av inre logik: Analysera slingans kropp för att bestämma dess komplexitet och multiplicera den med antalet iterationer.
* villkorade uttalanden (om/annars):
* Analysera både "if" och "annars" -blocken. Den övergripande komplexiteten är * maximalt * för komplexiteten i "if" och "annars" -blocken.
* För djupt kapslade "if/else" -strukturer, spåra försiktigt de möjliga exekveringsvägarna.
* rekursion:
* Identifiera basfallet: Dessa avslutar rekursionen.
* Identifiera det rekursiva steget: Hur problemet delas upp i mindre delproblem.
* Skriv en återfallsrelation: Detta beskriver matematiskt tidskomplexiteten för den rekursiva funktionen. Till exempel:`t (n) =t (n/2) + o (1)` (binär sökning)
* Lös återfallsrelationen: Använd metoder som Master Theorem, Substitution eller Recursion Tree för att hitta den asymptotiska tidskomplexiteten.
* Funktionssamtal: Tänk på tidskomplexiteten för den anropade funktionen. Om en funktion "A" -samtalsfunktion "b" kommer tidskomplexiteten för "a" att inkludera tidskomplexiteten för "B".
4. Expresskomplexitet i asymptotisk notation (Big O, Big Omega, Big Theta):
* Big O Notation (O): Representerar * övre gränsen * för algoritmens tillväxthastighet. Den beskriver det * värsta fallet * -scenariot. "Algoritmens tidskomplexitet är o (n^2)" betyder att algoritmen körtid inte kommer att växa * snabbare * än n^2 när 'n' ökar.
* Big Omega Notation (ω): Representerar * nedre gränsen * för algoritmens tillväxthastighet. Den beskriver * bästa fallet * -scenariot. "Algoritmens tidskomplexitet är ω (n)" betyder att algoritmen körtid inte kommer att växa * långsammare * än 'n' som 'n' ökar.
* Big Theta Notation (θ): Representerar den * täta bundet * för algoritmens tillväxthastighet. Den beskriver medelavfallsscenariot och när algoritmens runtime växer i samma takt som funktionen. "Algoritmens tidskomplexitet är θ (n log n)" betyder att algoritmens körtid kommer att växa i samma takt som n log n.
Vanliga tidskomplexiteter (värsta fall, Big O):
* o (1):konstant tid: Exekveringstiden är oberoende av ingångsstorleken. Exempel:Åtkomst till ett element i en matris med indexet.
* o (log n):logaritmisk tid: Exekveringstiden ökar logaritmiskt med ingångsstorleken. Exempel:Binär sökning i en sorterad matris.
* o (n):linjär tid: Exekveringstiden ökar linjärt med ingångsstorleken. Exempel:Söker efter ett element i en osorterad matris.
* o (n log n):Linearitmisk tid: Vanligt i effektiva sorteringsalgoritmer. Exempel:Merge Sort, Quicksort (genomsnittligt fall).
* o (n^2):Kvadratisk tid: Exekveringstiden ökar kvadratiskt med ingångsstorleken. Exempel:Bubble sortering, infogningssortering.
* o (n^3):kubiktid: Exempel:Matrismultiplikation.
* o (2^n):Exponentiell tid: Exekveringstiden fördubblas med varje tillägg till ingångsstorleken. Indikerar ofta en brute-force-strategi. Exempel:Försöker alla möjliga delmängder av en uppsättning.
* o (n!):Factorial Time: Exekveringstiden växer extremt snabbt. Exempel:Hitta alla permutationer av en uppsättning.
5. Ignorera ständiga faktorer och termer av lägre ordning:
När vi använder asymptotisk notation är vi främst intresserade av den * dominerande * termen som bestämmer tillväxttakten. Konstantfaktorer och termer av lägre ordning blir obetydliga eftersom 'n' växer mycket stora.
* `3n^2 + 5n + 10` förenklas till` o (n^2) `
* `100 log n + n` förenklas till` o (n) `(n växer snabbare än log n)
* `2^n + n^5` förenklas till` o (2^n) `
6. Analysera rymdkomplexitet:
I likhet med tidskomplexiteten, analysera det utrymme som används av algoritmen. Överväga:
* Ingångsutrymme: Det utrymme som krävs för att lagra inmatningsdata.
* hjälputrymme: Det extra utrymmet som används av algoritmen, bortom ingångsutrymmet, för variabler, datastrukturer och rekursionssamtal.
Exempel:
* linjär sökning:
`` `python
def linear_search (arr, mål):
för i inom räckvidd (len (arr)):
Om arr [i] ==Target:
returnera i
returnera -1
`` `
* Tidskomplexitet: O (n) (linjärt, värsta fall:Målet är inte i matrisen eller är det sista elementet)
* Rymdkomplexitet: O (1) (konstant, eftersom den bara använder några extra variabler)
* binär sökning:
`` `python
def binary_search (arr, mål):
låg =0
hög =len (arr) - 1
Medan låg <=hög:
Mid =(låg + hög) // 2
Om ARR [MID] ==Target:
Återgå mitt
elif arr [mid]
Låg =Mid + 1
annan:
hög =mitten - 1
returnera -1
`` `
* Tidskomplexitet: O (log n) (logaritmisk)
* Rymdkomplexitet: O (1) (konstant, iterativ version)
* Rekursiv binär sökning:
`` `python
def binary_search_recursive (arr, mål, låg, hög):
Om låg> hög:
returnera -1
Mid =(låg + hög) // 2
Om ARR [MID] ==Target:
Återgå mitt
elif arr [mid]
Return Binary_Search_Recursive (ARR, Target, Mid + 1, High)
annan:
Return Binary_Search_Recursive (ARR, Target, Low, Mid - 1)
`` `
* Tidskomplexitet: O (log n)
* Rymdkomplexitet: O (log n) på grund av rekursionsdjup. Varje rekursivt samtal lägger till en ny ram till samtalstacken.
Sammanfattningsvis:
1. Definiera vad du vill mäta: Tidskomplexitet, rymdkomplexitet eller båda.
2. Identifiera nyckeloperationerna bidrar till resursanvändning.
3. Analysera algoritmens struktur (Loops, Conditionals, Recursion).
4. Uttryck komplexiteten med Big O, Big Omega eller Big Theta -notation.
5. Ignorera ständiga faktorer och termer av lägre ordning.
Genom att följa dessa steg kan du effektivt analysera effektiviteten hos algoritmer och välja den lämpligaste algoritmen för dina specifika behov. Kom ihåg att den bästa algoritmen beror på det specifika problemet, storleken på inmatningsdata och tillgängliga resurser.
