You write a function that operates on an arbitrarily large volume of input.
Assuming that there is no bug - that it returns the right values every time (especially no infinite loops) - the only question now remains: how long does it take for the thing to finish?
Time is not an adequate means of measuring that because i could be running it on a better computer than you.
There are 3 ways of expressing time complexity, best case, worst case, and average case, and its performance depends on how "pre-sorted" the input already is and on the property of the algorithm itself.
Let us illustrate that with some sorting algorithms.
selection sort:
The selection sort iterates through every single element starting from the first index of the unsorted section, selecting the minimum, and places it to the front of the queue. Whatever input n is given, it takes n^2 steps to solve it. Therefore, the selection sort, worst case = best case = average case, running time can be expressed as: O(n^2)
quick sort:
the quick sort picks a pivot point and arranges two values at a time into the right order. The time complexity depends largely on how sorted the input already is. Therefore, worst case is O(n^2) if the input is a mess and it operates much like the selection sort. The best case is O(n log n) if the input is already sorted. The average case of the two is simply O(n) by simple algebra.
merge sort:
The merge sort takes a list of values and divide them into single elements, then compared each element with the adjacent list to merge into lists. The same process is repeated regardless of input, therefore, worst case = best case = average case, O(nlogn).
count sort
the count sort algorithm is usually used when the number of elements approximately equals to the number of possible key values.
There is only one case or runtime for count sort, and that is dependent on the size of input n and the number of key elements N
O(N + n)
Thursday, 27 March 2014
Monday, 24 March 2014
week of march 19, 2014 csc148h1 winter 2014
topic: Runtime analysis:
The binary search algorithm leads to the next question, how do you calculate the runtime of an algorithm?
We use O(n) as a mathematical function to represent the runtime.
The following are example models (which can be used in combination) the time a program could take to complete. Of course, time here is not measured in seconds (what if i have a better computer than you?) but in steps for n inputs.
The bellow mathematical models (stolen from the lecture slides) are very similar to the functions learned in high school math.
All these models (graphically) share the same "break even point" where a given n input produces the same runtime, but each function behaves arbitrarily different as the input becomes larger and larger.
To conclude, given lots and lots of input, with many many different methods of writing the code, the efficiency of the code should be kept in mind with the O(n) models.
The binary search algorithm leads to the next question, how do you calculate the runtime of an algorithm?
We use O(n) as a mathematical function to represent the runtime.
The following are example models (which can be used in combination) the time a program could take to complete. Of course, time here is not measured in seconds (what if i have a better computer than you?) but in steps for n inputs.
The bellow mathematical models (stolen from the lecture slides) are very similar to the functions learned in high school math.
All these models (graphically) share the same "break even point" where a given n input produces the same runtime, but each function behaves arbitrarily different as the input becomes larger and larger.
To conclude, given lots and lots of input, with many many different methods of writing the code, the efficiency of the code should be kept in mind with the O(n) models.
constant:
c
2
R
+
(some p ositive numb er)
logarithmic:
c
log
n
linear:
cn
(probably not the same
c
)
quadratic:
cn
2
cubic:
cn
3
exp onential:
c
2
n
horrible:
cn
n
or
cn
!
Where n is the input, and O(n) represent the "Worst case running time" of the code.
week of march 12, 2014 csc148h1 winter 2014
Topic(s): binary search
Assume a list in already-sorted order.
If you were asked to find a value within the list, how would you do it?
The simplest way would be to iterate through every single value in the list and check each value and return iff there is a value that match.
The question now becomes: how efficient is that?
If you were given a ridiculously long list and the target value is near the end of that ridiculously long list, that would take forever to such a point that you would doubt if your code will ever terminate.
There does exist a faster way of retrieving that value (providing that the list is sorted in order) - binary search.
The though process of it is that: assume the list in sorted order, you find the middle most value of the list, if the middle value is not the target value, you check whether it is bigger or smaller than the target value and ignore the other half of the list. The same process is recursed with the now half-sized list - find middle most value, if it != the target value, begin again on the half that contains the target value.
The complexity of this search sequence pays off in terms of time efficiency since the computer is only working with (1/2)^n of the content at all times.
Assume a list in already-sorted order.
If you were asked to find a value within the list, how would you do it?
The simplest way would be to iterate through every single value in the list and check each value and return iff there is a value that match.
The question now becomes: how efficient is that?
If you were given a ridiculously long list and the target value is near the end of that ridiculously long list, that would take forever to such a point that you would doubt if your code will ever terminate.
There does exist a faster way of retrieving that value (providing that the list is sorted in order) - binary search.
The though process of it is that: assume the list in sorted order, you find the middle most value of the list, if the middle value is not the target value, you check whether it is bigger or smaller than the target value and ignore the other half of the list. The same process is recursed with the now half-sized list - find middle most value, if it != the target value, begin again on the half that contains the target value.
The complexity of this search sequence pays off in terms of time efficiency since the computer is only working with (1/2)^n of the content at all times.
week of march 5, 2014 csc148h1 winter 2014
Topic: Linked Lists.
In this week, linked lists are introduced as a new ADT.
According to wikipedia:
a linked list is a data structure consisting of a group of nodes which together represent a sequence.
a linked list is created as a form of a class similar to other forms of Object Oriented Programming.
In the initializer, what is created is a variable, a variable with list as a beginning item and it has a reference to the next list, and that has a reference to the next list, and so on... The linked list shares a strong similarity with the already-learned queue ADT, in a sense that inserting values into the linked list is done in chronological order, one value after the other. The first noticeable distinction is that, while a queue will only remember the top most value in its chain, the linked list can be worked on in various ways: insert, delete, reverse order.
The structure of the linked list is also unique in a sense that each item is represented by a list. The following is the skeletal structure of a linked list: [list a] -> [list b] -> [list c]....
each item contains items, and has a reference to the next item.
Compared to other ADT's, the linked list shares the property of one item referencing to the next item like a tree, except there can only be one child, and it is also like a tuple, where it can only be operated one item at a time.
In this week, linked lists are introduced as a new ADT.
According to wikipedia:
a linked list is a data structure consisting of a group of nodes which together represent a sequence.
a linked list is created as a form of a class similar to other forms of Object Oriented Programming.
In the initializer, what is created is a variable, a variable with list as a beginning item and it has a reference to the next list, and that has a reference to the next list, and so on... The linked list shares a strong similarity with the already-learned queue ADT, in a sense that inserting values into the linked list is done in chronological order, one value after the other. The first noticeable distinction is that, while a queue will only remember the top most value in its chain, the linked list can be worked on in various ways: insert, delete, reverse order.
The structure of the linked list is also unique in a sense that each item is represented by a list. The following is the skeletal structure of a linked list: [list a] -> [list b] -> [list c]....
each item contains items, and has a reference to the next item.
Compared to other ADT's, the linked list shares the property of one item referencing to the next item like a tree, except there can only be one child, and it is also like a tuple, where it can only be operated one item at a time.
Subscribe to:
Posts (Atom)