COMPSCI 220代写、代写Java，c++程序

日期：2022-08-22 10:48

COMPSCI 220:

Algorithms and Data Structures

Slides and Pictures credited to Tanya Gvozdeva

Yan Kolezhitskiy Algorithms

Running time

Running time on inputs of the same size can be very different!

For example, consider an algorithm that looks for a letter in a

word. Suppose the word has only 3 letters. Then the following

are all possibilities:

the required letter is the first letter of the word;

the required letter is the second letter of the word;

the required letter is the third letter of the word;

the required letter is not in the word;

The number of operations is different in all these

possibilities!

Yan Kolezhitskiy Algorithms

THE WORST RUNNING TIME

Pros:

This is the worst possible!

If the worst running time is reasonable, then the algorithm

might be good.

Cons:

The worst-case might be achieved on some rare artificial

examples that essentially never occur in practice.

Even if the worst running time is pretty bad it does not

necessarily mean that the algorithm/program is not

practical!

Yan Kolezhitskiy Algorithms

THE WORST RUNNING TIME

Pros:

This is the worst possible!

If the worst running time is reasonable, then the algorithm

might be good.

Cons:

The worst-case might be achieved on some rare artificial

examples that essentially never occur in practice.

Even if the worst running time is pretty bad it does not

necessarily mean that the algorithm/program is not

practical!

Yan Kolezhitskiy Algorithms

THE BEST RUNNING TIME

Pros:

Usually it is very good!

Cons:

Very often (but not always) the best running time is rather

useless because there are some rare trivial inputs for

which everything is extremely great.

Yan Kolezhitskiy Algorithms

THE BEST RUNNING TIME

Pros:

Usually it is very good!

Cons:

Very often (but not always) the best running time is rather

useless because there are some rare trivial inputs for

which everything is extremely great.

Yan Kolezhitskiy Algorithms

THE AVERAGE RUNNING TIME

Pros:

The average over all inputs

Cons:

Do you take all theoretically possible inputs?

Do you restrict yourself only to some special inputs and

exclude “artificial” inputs from consideration? If so, how

exactly do you define “artificial”?

Should you consider every input as being equally likely? If

not, what is the most “natural” distribution?

Average time analysis very often involves quite a bit of

probability and ugly sums.

Even with the simplest distributions average running time

may not be easy to compute.

Yan Kolezhitskiy Algorithms

THE AVERAGE RUNNING TIME

Pros:

The average over all inputs

Cons:

Do you take all theoretically possible inputs?

Do you restrict yourself only to some special inputs and

exclude “artificial” inputs from consideration? If so, how

exactly do you define “artificial”?

Should you consider every input as being equally likely? If

not, what is the most “natural” distribution?

Average time analysis very often involves quite a bit of

probability and ugly sums.

Even with the simplest distributions average running time

may not be easy to compute.

Yan Kolezhitskiy Algorithms

THE AVERAGE RUNNING TIME

In these course we will usually consider all possible inputs and

will view them as equally likely

Yan Kolezhitskiy Algorithms

The best/worst/average running time should be defined for any

valid input n!