SkipCaptcha
292
edits
Changes
Jump to navigation
Jump to search
Line 15:
Line 15: + + + + + + + + + + + + + + + + + +
Added Categories and Complexity sections
There is a second type of algorithm - whereas most algorithms provably evaluate the most desirable end-state (for example, it is possible to mathematically prove that Dijkstra's algorithm gives the shortest route from one point to another) - others known as 'heuristic algorithms' cannot provably give the best solution (although they do give a fairly good result). While this may seem inferior, some problems are very difficult or even impossible to map out using normal algorithms, so heuristic ones are superior in these cases.
There is a second type of algorithm - whereas most algorithms provably evaluate the most desirable end-state (for example, it is possible to mathematically prove that Dijkstra's algorithm gives the shortest route from one point to another) - others known as 'heuristic algorithms' cannot provably give the best solution (although they do give a fairly good result). While this may seem inferior, some problems are very difficult or even impossible to map out using normal algorithms, so heuristic ones are superior in these cases.
==Computational Complexity==
One aspect of algorithms implemented in computer programs is that of computational complexity, which denotes how efficient (fast) they are. Asymptotic Notation is the formal means of describing the running time of an algorithm and the size of its inputs.<ref>Introduction to Computation and Programming Using Python by John V. Guttag</ref> The most commonly used notation is called "Big O", which is used to give an upper bound on the computational complexity of the routine. Some examples:
<ul>
<li><b>O(1)</b> indicates constant running time.</li>
<li><b>O(n)</b> indicates running time that is linear with the size of the inputs.</li>
<li><b>O(log n)</b> indicates running time that is logarithmic.</li>
<li><b>O(n<sup2>k</sup>)</b> indicates polynomial running time. For instance, O(n<sup>2</sup>) indicates that the algorithm is quadratic - that the running time increases as the square of the size of the input.</li>
</ul>
==Categories of Algorithms==
Algorithms can be categorized several ways.
===Pathfinding===
Pathfinding algorithms are commonly used. For instance, route finding apps on cell phones use pathfinding to determine the quickest route between two points. A-Star and Dijkstra's algorithm are examples of pathfinding algorithms.
===Greedy Algorithms===
Algorithms which find local optimizations instead of global optimizations are referred to as <b>greedy</b>. Although they may not return an optimal result, they tend to execute much faster than non-greedy algorithms.
==Examples of Algorithms==
==Examples of Algorithms==