Objective: Learn to analyze the time complexity of an algorithm
Download 45.54 Kb.
|
ComplexityObjective: Learn to analyze the time complexity of an algorithm. A task (problem) can be solved by different algorithms. The questions are: Whether there is an optimum algorithm? Which algorithm is the optimum? Criteria for choosing an algorithm: correctness easy to understand, implement and maintain clear and well documented efficient: space and time how much system resources it uses, i.e., memory - Space Complexity how fast it runs - Time Complexity To evaluate an algorithm efficiency, often we are interested in the rate of growth of the time or space required to solve larger instances of a kind of problem. We usually associate with a problem an integer, called the size of the problem, which measures the quantity of input data. The time needed by an algorithm expressed as a function of the size of a problem is called the time complexity of the algorithm. The limiting behavior of the time complexity when the size increases is called the asymptotic time complexity. Analogous definition can be made for the space complexity and asymptotic space complexity. It is the asymptotic complexity of an algorithm that ultimately determines the size of a problem that can be solved by the algorithm. T(n) , the time complexity function, is the measure of time taken by a program or an algorithm on any input of size n. We can think T(n) as the number of basic statements or operations executed by the program. However, we are not interested in the exact values of the function T(n), but rather in the rate of growth, or order of growth, of the running time. In many cases, we would like to find the upper bound of the complexity. We therefore consider only the leading term of a formula (e.g., aN2 ), since the lower-order terms are relatively insignificant for large N. Regarding an asymptotic upper bound, if an algorithm processes input of size N in time c*g(n) for some constant c, then, we say that the time complexity of the algorithm is O(g(n)). --- O-notation. O-notation is used to hide: average number of machine instructions a particular compiler generates average number of machine instructions a particular machine executes per second This helps to ignore computer and compiler related constants but it also allows us to make some simplifying assumptions. Running time of an algorithm depends on two things: size of input particular type of input Size of input: Example: Add n numbers If n = 5 then the following part of a program requires 17 units of time, T (n) = 5 int sum = 0; for (int i = 1; i<=5; i++) { sum = sum + i; }; As n increases we expect the running time to increase. If n is very small then even an inefficient algorithm will not have a long running time. Particular input: even if we consider the inputs having the same size, the number of operations performed by an algorithm may depend on the particular input. Example: An algorithm for alphabetizing a list of names may do very little work if only a few of the names are out of order, but it may have to do much more work on the list that is very scrambled. Andrea Penny David David Cathy Evelyn Evelyn Cathy Penny Andrea Therefore, the number of steps an algorithm takes depends on not just the size of input values, but also the particular types of input values.
Best case running time -- the least running time on any input among all inputs of size n. Average case running time – the average running time of the program over all inputs of size n. more realistic but harder to compute Worst case running time -- the maximum running time on any input among all inputs of size n. We usually concentrate on finding only the worst-case running time, that is, the longest running time for any input of size n. Its reasons are: the worst case is an upper bound, the worst case occurs fairly often for some algorithms, the average case is sometimes roughly as bad as the worst case. The average-case running time of an algorithm is interested in some situations. Example: Suppose that we pick a program whose running time is as follows: T (n) = c(n+ 1)2 = cn2 + 2cn + c We say that T(n) is O(n2). This gives us a way of seeing how the value n, the size of input, affects the algorithm.
Constant factors do not matter Ex. T (n) = 6n, we say that T(n) is O(n). Low order terms do not matter and can be ignored T (n) = 4n5 + 3n4..., we say that T(n) = O(n5). Common Order Classes of algorithms: O(1) Constant O(log n) logarithmic O (n) Linear O(n log n) n log n O(n2) quadratic O(n3) cubic O(2n) exponential An algorithm in O (1) is said to have a constant time complexity. This kind of algorithm is independent of the problem size. Ex., an algorithm that prints one element of an array has the running time which is independent of the size of the array. Operation rules: Summation rule: Assume T1 (n) is O(f(n)), and T2(n) is O(g(n)) ,where f(n) and g(n) are functions defined on n, T1and T2 are running times of algorithm 1 and algorithm 2 respectively, then T1+ T2 is O(max(f(n), g(n))). Example: T1 = O(n2), T2 = O(n3) T2 will dominate, hence T1 + T2 = T2 = O (n3) Product rule: Assume T1 (n) is O(f (n)) and T2(n) is O(g (n)), then T1 * T2 is T1(f (n) *g (n)). Transitive law if f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) is O(h(n)). Analysis of instructions to determine a running time: Simple statements are O(1). Assignment, addition, multiplication, or accessing an array takes constant amount of time O(1). 2. Conditional statement if ( condition ) { True part statements; } else {
False part statements; }
time taken to evaluate the condition t time taken for true part time taken for false part Overall time for a conditional statement is the time taken to evaluate the condition plus maximum time for true part or false part. if the time to evaluate the condition is O(1) then that can be ignored If the if statement is a nested statement: if (condition) { statements; } else if (condition ){ statements; } … else {statements; } Assuming that there are no method calls in the conditions. The running time for the if is the running time of the part that takes the most time. 3. for loops running time is the production result of : the limits specified in the for statement (the limit of the loop indicates the number of times the loop will be executed) the time to run the body of the loop Ex. To get the overall time complexity for loops: get the number of times the loop is to be executed n (= upper limit-lower limit + 1) for (int i = 1; i== n; i++) {statements;} Obtain the amount of time spent in one iteration which includes: Steps performed once: time to initialize the loop index is 1 (constant time O(1)). time to test the loop index the first time is 1 (constant time O(1)). Steps performed the number of times the loop is executed: time to test the loop index is 1 (constant time O(1)) the time to increment the loop index is 1 (constant time O(1)). In general these constant times can be dropped by the rule of summation. Example 1: for loop int a; int sum = 0; for (int i= 1; i = = n; i++) { a = i*2; sum = sum + a; } The loop is executed n times, and the running time of the body of the loop is 2. Therefore, T(n) = 2n, the time complexity for the loop is O(n). Download 45.54 Kb. Share with your friends:
|