Optimization - Revision history

Brian at 01:34, 5 January 2012

2012-01-05T01:34:53Z

Brian at 08:38, 4 January 2012

2012-01-04T08:38:16Z

Brian: Created page with "''This article is about improving programs. For the class of problems, see optimization problem.'' To '''optimize''' a correct program is to engineer its [[Algorithm|design ..."

2011-06-29T15:41:32Z

Created page with "''This article is about improving programs. For the class of problems, see optimization problem.'' To '''optimize''' a correct program is to engineer its [[Algorithm|design ..."

New page

''This article is about improving programs. For the class of problems, see [[optimization problem]].''

To '''optimize''' a correct program is to engineer its [[Algorithm|design or implementation]] to improve its performance. This generally means decreasing its [[Asymptotic analysis|time complexity]], [[Asymptotic analysis|space complexity]], CPU time usage, or memory usage. Sometimes it will be possible to decrease all of these, whereas in other cases one might be sacrificed for another (especially in the so-called ''time/memory tradeoff''). Less commonly in algorithmic programming, optimization can also mean reducing disk seeks, cache faults, or response time, or increasing throughput. A specific concept that optimizes a program, such as I/O buffering, is also referred to as ''an optimization''. Generally, optimization improves the targeted performance statistic for all or almost all conceivable inputs, or the improvements it offers vastly outweigh the regressions (for example, a program may run slightly more slowly on very small inputs but significantly more quickly on medium to large inputs after optimizations have been made). It thus improves performance in both the average case and the worst case. When the average case performance is already excellent but the worst case performance needs improvement, [[randomization]] may be easier than optimization.

@@ Line 11: / Line 11: @@
 # Don't do anything stupid. Don't do anything twice.
 }}
 ==References==
 <references/>

← Older revision		Revision as of 08:38, 4 January 2012
Line 2:		Line 2:

	To '''optimize''' a correct program is to engineer its [[Algorithm\|design or implementation]] to improve its performance. This generally means decreasing its [[Asymptotic analysis\|time complexity]], [[Asymptotic analysis\|space complexity]], CPU time usage, or memory usage. Sometimes it will be possible to decrease all of these, whereas in other cases one might be sacrificed for another (especially in the so-called ''time/memory tradeoff''). Less commonly in algorithmic programming, optimization can also mean reducing disk seeks, cache faults, or response time, or increasing throughput. A specific concept that optimizes a program, such as I/O buffering, is also referred to as ''an optimization''. Generally, optimization improves the targeted performance statistic for all or almost all conceivable inputs, or the improvements it offers vastly outweigh the regressions (for example, a program may run slightly more slowly on very small inputs but significantly more quickly on medium to large inputs after optimizations have been made). It thus improves performance in both the average case and the worst case. When the average case performance is already excellent but the worst case performance needs improvement, [[randomization]] may be easier than optimization.		To '''optimize''' a correct program is to engineer its [[Algorithm\|design or implementation]] to improve its performance. This generally means decreasing its [[Asymptotic analysis\|time complexity]], [[Asymptotic analysis\|space complexity]], CPU time usage, or memory usage. Sometimes it will be possible to decrease all of these, whereas in other cases one might be sacrificed for another (especially in the so-called ''time/memory tradeoff''). Less commonly in algorithmic programming, optimization can also mean reducing disk seeks, cache faults, or response time, or increasing throughput. A specific concept that optimizes a program, such as I/O buffering, is also referred to as ''an optimization''. Generally, optimization improves the targeted performance statistic for all or almost all conceivable inputs, or the improvements it offers vastly outweigh the regressions (for example, a program may run slightly more slowly on very small inputs but significantly more quickly on medium to large inputs after optimizations have been made). It thus improves performance in both the average case and the worst case. When the average case performance is already excellent but the worst case performance needs improvement, [[randomization]] may be easier than optimization.
		+
		+	For optimizations that do not affect asymptotic (scaling) behaviour, but improve time or memory usage by a constant factor only, see [[invisible constant factor]].
		+
		+	==Pruning==
		+	In [[recursive]] backtracking algorithms, the central tenet of optimization is the following:<ref name="usaco">''Optimization Techniques''. USACO Training Pages, Section 4.1</ref>
		+	{{ImportantConceptBox\|
		+	# Prune early, prune often.
		+	# Don't do anything stupid. Don't do anything twice.
		+	}}
		+
		+	==References==
		+	<references/>