Algorithms what is backtracking
) what are the different notations used to measure the time complexity
Download 127.59 Kb.
|
1 2
7) what are the different notations used to measure the time complexityA)Related asymptotic notations: O, o, Ω, ω, Θ, ÕBig O is the most commonly used asymptotic notation for comparing functions, although in many cases Big O may be replaced with Θ for asymptotically tighter bounds (Theta). Here, we define some related notations in terms of "big O": 8) How the efficiency of an algorithm is measuredA) Algorithmic efficiencyEfficiency is generally contained in two properties: speed, (the time it takes for an operation to complete), and space, (the memory or non-volatile storage used up by the construct). Optimization is the process of making code as efficient as possible, sometimes focusing on space at the cost of speed, or vice versa. The speed of an algorithm is measured in various ways. The most common method uses time complexity to determine the Big –oh of an algorithm: often, it is possible to make an algorithm faster at the expense of space. This is the case whenever you cache the result of an expensive calculation rather than recalculating it on demand. The space of an algorithm is actually two separate but related things. The first part is the space taken up by the compiled executable on disk (or equivalent, depending on the hardware and language) by the algorithm. 9) what is space complexityA) Space complexityThe better the time complexity of an algorithm is, the faster the algorithm will carry out his work in practice. Apart from time complexity, its space complexity is also important: This is essentially the number of memory cells which an algorithm needs. A good algorithm keeps this number as small as possible, too. There is often a time-space-tradeoff involved in a problem, that is, it cannot be solved with few computing time and low memory consumption. One then has to make a compromise and to exchange computing time for memory consumption or vice versa, depending on which algorithm one chooses and how one parameterizes it. 10) what are the best , average and worst case complexities of (selection , bubble insertion ,quick , heap ,merge sorting methods) A) ClassificationFor typical sorting algorithms good behavior is O (n log n) and bad behavior is Ω(n2). Ideal behavior for a sort is O(n). Sort algorithms which only use an abstract key comparison operation always need at least Ω(n log n) comparisons on average. List of sorting algorithmsIn this table, n is the number of records to be sorted and k is the average length of the keys. The columns "Best", "Average", and "Worst" give the time complexity in each case; estimates that do not use k assume k to be constant. "Memory" denotes the amount of auxiliary storage needed beyond that used by the list itself..
11) wat is an inplace and non-inplace algorithms A) An algorithm which is not in-place is sometimes called not-in-place or out-of-placeAn algorithm is sometimes informally called in-place as long as it overwrites its input with its output. In reality this is not sufficient (as the case of quicksort demonstrates) nor is it necessary; the output space may be constant, or may not even be counted, for example if the output is to a stream. On the other hand, sometimes it may be more practical to count the output space in determining whether an algorithm is in-place, such as in the first reverse example below; this makes it difficult to strictly define in-place algorithms. 12) What is the order of an algorithm which perfrms matrix multiplicationA) The order of the matrix multiplication using strassens matrix multiplication is n2.80713) What is the best , average and worse case complexities of an algorithmA)Time complexity in the best case measures the leaset amount of time that the algorithms needs to solve an instance of the problemTime complexity in the worse case measures the largest amount of time that the algorithms needs to solve an instance of the problemTime complexity in the average case measures the average amount of time that the algorithms needs to solve an instance of the problem14) what is the best case average case and worse time complexities of binary search and linear searchA) Complexity of linear search for successful searchesBest case Ө(1)Average case Ө(log n)Worse case Ө(log n)Complexity of linear search for unsuccessful searchesBest case Ө(logn)Average case Ө(log n)Worse case Ө(log n)Complexity of binary searchBest case Ө(logn)Average case Ө(log n)Worse case Ө(log n)15) Which sorting algorithms has very high space complexityA) Merge sort takes high space complexity16) how many maximum comparisions are required o search a key in binary search treeA) The number of element comparisions is atmost k for a successful is in the rane of (2k-1 ,2k) for binary search tree. For unsuccessful search the element comparision are either K or k-1. unsuccessful complexity is Ө(logn). For successful search the element comparision are either K or k-1. unsuccessful complexity is O(logn)17) what is a passA) It is an iteration or one time execution of a loop for n times18)what is the best , average and worse case time complexity of the push operation of a stackA) It is O(1)19) what is the best , average and worse case time complexity of the pop operation of a stackA) It is O(1)20) what is the best , average and worse case time complexity of the insert and delete operations of a queueA) It is O(n) for insert and O(1) for delete operationsDirectory: images images -> Pelan pentaksiran kursus images -> Military callsign list as of dec 2010 images -> For Date: 02/01/2013 Friday Call Number Time Call Reason Action 13-768 0008 motor vehicle stop warning Issued images -> New embedded S images -> Creating Buy-In – Building Relationships images -> Deadline: Saturday, March 12th, 2016 images -> News items from Raising Our Voices images -> Last year four of the best Afrikaans Christian singers joined forces to tour Down Under with the production ‘Manne wat Glo’ images -> World-renowned vocal ensemble sweet honey in the rock images -> Peoples Voice Café History Download 127.59 Kb. Share with your friends:
|
1 2