टेम्पलेट:कंप्यूटर-बिज्ञान-आधार: रिवीजन सभ के बीचा में अंतर

Content deleted Content added
imported>Svick
removed "external link" icon
imported>Aaron.mer
Begginings of the wikipage
लाइन 1:
== Best Case Complexity ==
 
Often when dealing with computer algorithms it is not only useful to know [[Worst case complexity]], it is also important to know what is the best case time for an algorithm. Formally the best case complexity is Inf(S) where S is the set of all g(n) such that T(n) = _Omega( g( n ) )''(T(n) is in Big Omega of g(n))''.
 
ie.- '''Best Case Complexity b = {inf(S) | S = \-/ f s.t f <= c * g(n) } '''
 
A very trivial example of this would be the code in java:
 
public static void main(String[] args){
for (int i = 0;i < agrs[1].toInt() ; i++){
System.out.println("" + i);
}
}
 
The worst case complexity for this algorithm is the same as its best case. This algorith is in _Omega( n ).
In many cases however Best case does not equal Worst case. In these cases it is quite easy to find a g(n) such that T(n) = _Omega(g(n)), finding the tight bound ie. the inf(S) requires looking at possible sequences that yeilds the best results.
 
Ie. for a [Bubble Sort] modified to check for a sorted list the worst case is n^2 while the best case''(a list already in sorted order)'' yields a best case of _Omega(n) even though its a trivial case.
 
== See also ==
* [[Average case complexity]]
* [[Worst case complexity]]
* [[Big O notation]]
 
== References ==
Preiss, Bruno R., [http://www.brpreiss.com/books/opus5/html/book.html Data Structures and Algorithms with Object-Oriented Design Patterns in Java],Waterloo.
 
 
 
 
 
<div class="boilerplate metadata" id="stub">[[Image:LampFlowchart.svg|20px|Comp Sci logo]]&nbsp;''This [[computer science]]-related article is a [[WP:Stub|stub]]. You can [[Wikipedia:Find or fix a stub|help]] Wikipedia by <span class="plainlinks">[{{SERVER}}/w/index.php?stub&title={{FULLPAGENAMEE}}&action=edit expanding it]</span>''.</div>[[Category:Computer science stubs<noinclude>| </noinclude>]]<noinclude>[[Category:WikiProject Computer science]]
</noinclude>