Karteikarten
How can we measure how good an algorithm is?
Karten in diesem Stapel (12)
- 1Give two different resources used by an algorithm that we might measure.Time taken to execute, and memory used while executing.
- 2Why do we usually measure the time taken by an algorithm rather than the time taken by an implementation of an algorithm?The time taken by an implementation varies depending on the programming language chosen, the quality of the compiler used, and the processor on which the program is executed. There are a vast number of combinations of these variables, so it is not worthwhile to study the implementations of algorithms. The result we get will therefore be machine-independent.
- 3What are the basic general principles behind measureing the tiem taken by some algorithm, expressed using pseudocode, on some particular input?we work only with algorithms in the strong expectation that our analysis will be machine independent but still closely related to and reflective of the time taken by any implementation on any given processor. We assume that the variables can be manipulated in a small, fixed numbero f units of time, as can basic operations involving variables. So, for example, an assignmente of a value to a variable or a comparison of two variables can be done in at most c (fixed integer) units of time. A general philosophy is: any basic algorithmic operation can be undertaken in at most c units of time. Analysis of algorithms is purposefully imprecise and this approach hides and works around (what often turns out to be) unimportant details.
- big-O notation is often used.
-We focus on the time taken compared to the size of the input, and ignore constants. - 4In pseudo-code we assume that any basic instruction takes c units of time to execute. What is this constant c supposed to reflect?c is a fixed integer that reflects the actual processor upon which the algorithm is eventually implemented and exectued, and it represents the time it takes for that specific processor to execute the instruction under that specific implementation.
- 5What is the worst-case time complexity of an algorithm? Why is it expressed as a function on the natural numbers?The worst-case time complexity is a function of the longest possile runtime of the algorithm. It is expressed as a function on the size of the input of an algorithm (always a natural number), using a notation that suppresses constants as they are irrelevant, called Big-O notation. As input size increases, so does algorithm runtime, the information we are looking ofr is the scale of that runtime increase - is it linearly based on the size of the input? Logarithmically based? Polynomially? Exponentially?
- 6—For two functions f, g : N -> N, f=O(g) if there exists some n0 ∈ N and some positive rational k ∈ Q s.t. f(n) <= kg(n) whenever n >= n0
- 7—
- 8Suppose that you had two algorithms to solve some problem that had time complexities O(n^3) and O(n^2) and two computers, one of which was 100 times faster than the other, but you can only run the slower algorithm on the faster machine and the faster on the slower machine. Say which configuration you would use to solve your problem and why.For inputs of size <= 100 I would use the slower algorithm on the faster machine. For inputs greater, then I would use the faster algorithm on the slower machine. This is because 100^3/100 = 100^2. While the increase in n means that the faster algorithm is better eventually, the increased speed of the computer with the slower algorithm is enough to mean that for smaller inputs, this algorithm takes less time.
- 9Define precisely what we mean when we say that two functions f(n) : N-> N and g(n) : N-> N are such that f = Ω(g). What does it mean in practice if we say that any algorithm solving the sorting problem has time complexity Ω(nlog(n))?Fo two functions f,g : N->N we write g = Ω(f(n)) if there exists some n0 ∈ N and some positive rational k ∈ Q such that g(n) >= kf(n) whenever n >= n0.
Big omega provides the lower bound for the growth of a function.
Any comparison based sorting algorithm will have complexity of at least n log n, so if this is achieved, we cannot better it. - 10Define precisely what we mean when we say that two functions f(n) : N-> N and g(n) : N-> N are such that f = ϴ(g). What does it mean in practice if we say that any algorithm solving the sorting problem has time complexity ϴ(nlog(n))?For two functions f,g : N -> N, we write f(n) = ϴ(g(n)) ifff f = O(g(n)) and f = Ω(g(n)).
Big Theta implies a tight bound, ie if we have some constants c1 and c2, f(n) will be bounded between g(n)*c1 and g(n)*c2.
Any sorting algorithm will have complexity of nlog(n), no more and no less. - 11—The complexity of bubble sort is O(n^2). In the worst case, the list is in reverse order, and the algorithm will perform n swaps in the first row, n-1 swaps in the second, n-2 in the third, etc, until performing 1 swap in the last row. Since this algorithm is not improved in any way, it will undertake n-1 comparisons for every row. Since it will take n rows to complete (as stated above), and uses n-1 comparisons for every row, n(n-1) operations are performed. It then takes n operations to output the list.
time complexity = O((n-1)n + n)
-> f(n) = O(n^2)
- 12What is the time complexity of Selection-sort? Explain.O(n^2).
The algorithm iterates through n-1 values in the list to find the smallest value on the first pass, then n-2 for the next smallest, etc, performing this many comparisons for each pass too. It takes n operations to output A.
Thus O(((n-1)/2)^2 + n) = O(n^2).
Informationen
- Beschreibung
- Karteikarten am How can we measure how good an algorithm is?, erstellt von SEZ McKelvey am 10/04/2018.
- Erstellt von
- SEZ McKelvey
- Aufrufe
- 0
- Bewertung
Mehr zu Algorithm Analysis and Complexity