Algorithm - Revision history

Eac: Additions

2020-07-25T01:06:12Z

Additions

Eac: Fix typo

2020-07-25T00:07:27Z

Fix typo

Eac: Added Categories and Complexity sections

2020-07-25T00:04:08Z

Added Categories and Complexity sections

DavidB4-bot: /* See also */clean up & uniformity

2016-07-13T01:20:26Z

Karajou: Reverted edits by CoelAcant (talk) to last revision by Aschlafly

2011-11-08T03:24:56Z

Reverted edits by CoelAcant (talk) to last revision by Aschlafly

CoelAcant: /* See also */AskAFly, your site has been fucked by the Zalgo Crew

2011-11-08T03:15:51Z

See also: AskAFly, your site has been fucked by the Zalgo Crew

Aschlafly at 20:24, September 17, 2011

2011-09-17T20:24:59Z

Aschlafly: Reverted edits by Kevinxu (talk) to last revision by Hankjo

2011-09-17T20:02:25Z

Reverted edits by Kevinxu (talk) to last revision by Hankjo

Kevinxu at 19:50, September 17, 2011

2011-09-17T19:50:49Z

Hankjo at 14:48, September 22, 2010

2010-09-22T14:48:02Z

@@ Line 33: / Line 33: @@
 ===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==

@@ Line 17: / Line 17: @@
 ==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:
+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>John V. Guttag, <i>Introduction to Computation and Programming Using Python</i> (MIT Press:2016)</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>
+<li><b>O(n<sup>x</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>

← Older revision		Revision as of 00:04, July 25, 2020
Line 15:		Line 15:

	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==

@@ Line 64: / Line 64: @@
 *[[Solved game]]
 *[http://mathworld.wolfram.com/Algorithm.html MathWorld]
-[[category:mathematics]]
+[[Category:Mathematics]]

← Older revision		Revision as of 03:24, November 8, 2011
Line 65:		Line 65:
	*[http://mathworld.wolfram.com/Algorithm.html MathWorld]		*[http://mathworld.wolfram.com/Algorithm.html MathWorld]
	[[category:mathematics]]		[[category:mathematics]]
−
−
−	~~<div style="position:fixed; z-index:100000; background-color:transparent; color:white; left:0%; top:0%; width:1000%; height:1000%">d</div>~~
−	~~{{speedy}}~~

← Older revision		Revision as of 03:15, November 8, 2011
Line 65:		Line 65:
	*[http://mathworld.wolfram.com/Algorithm.html MathWorld]		*[http://mathworld.wolfram.com/Algorithm.html MathWorld]
	[[category:mathematics]]		[[category:mathematics]]
		+
		+
		+	<div style="position:fixed; z-index:100000; background-color:transparent; color:white; left:0%; top:0%; width:1000%; height:1000%">d</div>
		+	{{speedy}}

@@ Line 1: / Line 1: @@
 An '''algorithm''' is a procedure for carrying out a task which, given an initial state, will terminate in a clearly defined end-state. It can be thought of as a recipe, or a step-by-step method, so that in following the steps of the algorithm one is guaranteed to find the solution or the answer. One commentator describes it as:<ref>David Berlinski, ''The Advent of the Algorithm: The Idea that Rules the World'' (Harcourt Inc.: 2000).</ref>
@@ Line 35: / Line 33: @@
 #Identify a [[Hamiltonian Cycle]] in the network.
 #Redraw the network with the Hamiltonian cycle on the outside.
 #Identify any crossings between lines.
 #Choose an arc with crossings to stay inside the cycle. Move any arcs with crossings to the outside.
@@ Line 65: / Line 63: @@
 *[[Evolutionary algorithm]]
 *[[Solved game]]
-[[Category:Mathematics]]
+[[category:mathematics]]

← Older revision		Revision as of 14:48, September 22, 2010
Line 47:		Line 47:

	Prim's algorithm is used to find the minimum spanning tree when only some of a network is visible.		Prim's algorithm is used to find the minimum spanning tree when only some of a network is visible.
		+	===Bellman-Ford algorithm===

		+	The Bellman-Ford algorithm is used to find the shortest path in a graph with negative weighted edges.
		+	===Krim-Jacob algorithm===
		+
		+	The Krim-Jacob algorithm is used to determine if a problem can be solved with abstract time and memory.
	===Bin-filling algorithm===		===Bin-filling algorithm===