To understand how an algorithm can perform on different sizes of input we need to analyze the algorithm in different cases. and to compute the best, average, and worst running time of an algorithm we need to consider three cases of an algorithm.
Analysis of algorithm
suppose we have an algorithm as shown in the given below image. and we run this algorithm on different inputs and for every input, the running time for the algorithm is different. as you see in the image. so, in this case, to analyze the algorithm in particular inputs we consider three cases.
Three cases of algorithm
- Worst case
- Best case
- Average case
Worst-case analysis of the algorithm
It’s a case when an algorithm will take a maximum running time for input size n to execute. let’s say we are searching for an element in an array using a searching algorithm then if an element is found at the last index then it’s a worst-case for the algorithm.
So generally we consider an input for which the algorithm takes the longest time to execute.
Note – The worst case is very informative and is usually done because an algorithm can’t execute in a time that is greater than the worst case.
Best-case analysis of the algorithm
It’s a case when the algorithm will take the minimum running time for an input size.
For example, if we search for an element in an array and we found that array at the first element of an array. then it’s a best-case for an algorithm. so generally to compute the best case of an algorithm, we consider an input for which the algorithm takes the shortest time.
Note: this case is not very informative because it doesn’t show the real execution time of an algorithm.
Average case analysis of an algorithm
It’s a case when an algorithm takes an average running time for an input size n to execute. let’s say we search for an element in an array and the element is found in the middle of the array. then it’s an average case for the algorithm.
so usually to compute the average case of an algorithm, we consider all possible inputs and compute the average running time.
Note: generally it’s very difficult to compute the average case. because the input size is very on a number of terms.
Kuelewa jinsi algorithm inaweza kufanya juu ya ukubwa tofauti ya pembejeo tunahitaji kuchambua algorithm katika kesi tofauti. Ili kuamua kiwango cha juu, wastani, na kiwango cha chini cha algorithm, ni muhimu kuzingatia mambo matatu. Uchambuzi wa algorithm kudhani tuna algorithm kama inavyoonyeshwa katika picha iliyotolewa chini. Algorithm hii inaendesha kwa kila pembejeo tofauti, na kwa kila pembejeo, muda wa kuendesha ni tofauti. Kama unavyoona kwenye picha. Kwa hiyo, katika kesi hii, kuchambua algorithm katika pembejeo maalum sisi kuzingatia kesi tatu. Matukio matatu ya algorithm - mbaya zaidi kesi - bora kesi - wastani kesi mbaya zaidi kesi uchambuzi wa algorithm Ni kesi wakati algorithm itachukua muda wa juu wa kukimbia kwa ukubwa wa pembejeo n kutekeleza. hebu kusema sisi ni kutafuta kwa ajili ya kipengele katika safu kwa kutumia algorithm kutafuta basi kama kipengele ni kupatikana katika index ya mwisho basi ni mbaya-kesi kwa algorithm. Kwa hiyo kwa ujumla sisi kuzingatia pembejeo ambayo algorithm inachukua muda mrefu zaidi kutekeleza. Kumbuka <unk> Hali mbaya ni habari sana na ni kawaida kufanyika kwa sababu algorithm haiwezi kutekeleza katika muda ambayo ni kubwa kuliko hali mbaya. Uchambuzi bora-kesi ya algorithm Ni kesi wakati algorithm itachukua muda wa chini wa kukimbia kwa ukubwa wa pembejeo. Kwa mfano, kama sisi kutafuta kwa ajili ya kipengele katika safu na sisi kupatikana kwamba safu katika kipengele cha kwanza cha safu. basi ni bora-kesi kwa ajili ya algorithm. Kwa hivyo kwa ujumla kuhesabu kesi bora ya algorithm, tunazingatia pembejeo ambayo algorithm inachukua muda mfupi zaidi. Kumbuka: kesi hii si habari sana kwa sababu haina kuonyesha wakati halisi wa utekelezaji wa algorithm. wastani kesi uchambuzi wa algorithm Ni kesi wakati algorithm inachukua wastani wa kukimbia muda kwa ukubwa wa pembejeo n kutekeleza. hebu kusema sisi kutafuta kwa ajili ya kipengele katika safu na kipengele ni kupatikana katika katikati ya safu. basi ni kesi ya wastani kwa ajili ya algorithm. Kwa hivyo kwa kawaida kuhesabu kesi ya wastani ya algorithm, tunazingatia pembejeo zote zinazowezekana na kuhesabu muda wa wastani wa kukimbia. Kumbuka: kwa ujumla ni vigumu sana kuhesabu kesi ya wastani. Kwa sababu ukubwa wa pembejeo ni kubwa sana katika idadi ya masharti.