CPSC 319 Lecture Notes - Lecture 2: Longest Path Problem, Mathematical Proof, Dspace
14 Apr 2017
School
Department
Course
Professor
Document Summary
Correct: must be shown to work for all possible inputs. Efficient: we prefer algorithms that minimize running time and memory usage, especially for large inputs. Complexity is a measure of the difficulty of performing a computation in terms of: Computational complexity: the number of steps or arithmetic operations required. Space complexity: the amount of memory required. Complexity analysis of an algorithm reveals how the time or space it requires to solve a problem varies with input data size. Is expressed as a function of n (number of inputs) We could analyze complexity empirically i. e. code and run the algorithm, measuring the time and memory used. The results are affected by: processor speed, ram and disk access time, code produced by the compiler. Other limitations: cannot test all possible inputs, cannot compare results unless experiments are done in the same environment, must fully implement the algorithm to test it. We prefer to analyze the algorithm directly, ignoring its implementation.
