CPSC 319 Lecture Notes - Lecture 2: Longest Path Problem, Mathematical Proof, Dspace

69 views5 pages

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.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents