CS234 Lecture Notes - Random-Access Machine, Ais People, Polynomial
4 Feb 2014
School
Department
Course
Professor
Document Summary
It is a sequence of well-define steps for solving a given problem. For a problem p, we may have multiple algorithms. For every algorithm a, we may have multiple implementations. Influenced by processor, memory, os, complier, pl : you cannot test for all inputs. Complexity analysis (pencil and paper approach: examine the algorithm. Example: write an algorithm to find the sum of the first n numbers. Random access machine (ram) model: memory accesses take constant time, primitive operations take constant time, comparisons, arithmetic operations, assignment. Measuring time complexity: given the size of input n, sum the number of memory accesses, sum the number of primitive operations in the algorithm, derive a formula t(n) T(n) is approximately the number of steps in the algorithm in terms of the input size. Analysis types: worst case most common approach, simpler, crucial, best case almost always faster on certain inputs, average case difficult. T(n) is o(f(n)) t(n) is bounded from above by f(n)
