Java Reference
In-Depth Information
2.
An input that results in the shortest execution time is called the
best-case
input and one
that results in the longest execution time is called the
worst-case
input. Best case and
worst case are not representative, but worst-case analysis is very useful. You can be
assured that the algorithm will never be slower than the worst case.
3.
An
average-case analysis
attempts to determine the average amount of time among all
possible input of the same size. Average-case analysis is ideal, but difficult to perform,
because for many problems it is hard to determine the relative probabilities and distribu-
tions of various input instances.
4.
If the time is not related to the input size, the algorithm is said to take
constant time
with
the notation
O
(1).
5.
Linear search takes
O
(
n
) time. An algorithm with the
O
(
n
) time complexity is called a
linear algorithm
and it exhibits a linear growth rate. Binary search takes
O
(log
n
) time.
An algorithm with the
O
(log
n
) time complexity is called a
logarithmic algorithm
, and
it exhibits a logarithmic growth rate.
6.
The worst-time complexity for selection sort is
O
(
n
2
). An algorithm with the
O
(
n
2
) time
complexity is called a
quadratic algorithm
, and it exhibits a quadratic growth rate.
7.
The time complexity for the Tower of Hanoi problem is
O
(2
n
). An algorithm with the
O
(2
n
) time complexity is called an
exponential algorithm
, and it exhibits an exponential
growth rate.
8.
A Fibonacci number at a given index can be found in
O
(
n
) time using dynamic
programming.
9.
Dynamic programming is the process of solving subproblems, then combining the solu-
tions of the subproblems to obtain an overall solution. The key idea behind dynamic
programming is to solve each subproblem only once and store the results for subprob-
lems for later use to avoid redundant computing of the subproblems.
10.
Euclid's GCD algorithm takes
O
(log
n
) time.
n
n
log
n
2
11.
¢
≤
All prime numbers less than or equal to
n
can be found in
O
time.
12.
The closest pair can be found in
O
(
n
log
n
) time using the
divide-and-conquer approach
.
13.
The divide-and-conquer approach divides the problem into subproblems, solves the
subproblems, then combines the solutions of the subproblems to obtain the solution for
the entire problem. Unlike the dynamic programming approach, the subproblems in the
divide-and-conquer approach don't overlap. A subproblem is like the original problem
with a smaller size, so you can apply recursion to solve the problem.
14.
The Eight Queens problem can be solved using backtracking.
15.
The backtracking approach searches for a candidate solution incrementally, abandoning
that option as soon as it determines that the candidate cannot possibly be a valid solu-
tion, and then looks for a new candidate.
16.
A
convex hull
for a set of points can be found in
O
(
n
2
) time using the gift-wrapping
algorithm and in
O
(
n
log
n
) time using the Graham's algorithm.
Search WWH ::
Custom Search