Since the number of permutations of n objects is equal to n-factorial (n! or n ??—
(n??’1) ??— (n??’2) ... ??— 2 ??— 1), the number of routes to test grows as the factorial of the number of cities, divided by 2.
So the order of growth for the TSP problem is n-factorial; ??(n!).
24 ALGORITHMS [CHAP. 2
Figure 2-2 Comparison of orders of growth.
Q Classification
k Constant: run time is fixed, and does not depend upon n. Most instructions are executed once,
or only a few times, regardless of the amount of information being processed.
lg n Logarithmic: when n increases, so does run time, but much more slowly than n does. When n
doubles, lg n increases by a constant, but does not double until n increases to n2. Common in
programs which solve large problems by transforming them into smaller problems.
n Linear: run time varies directly with n. Typically, a small amount of processing is done on
each element.
n lg n When n doubles, run time slightly more than doubles. Common in programs which break
a problem down into smaller subproblems, solve them independently, and then combine
solutions.
n2 Quadratic: when n doubles, runtime increases fourfold. Practical only for small problems;
typically the program processes all pairs of input (e.
Pages:
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73