tailieunhanh - Lecture Algorithms and data structures: Chapter 19 - Algorithm Analysis

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. This chapter introduce perfect binary trees: Definitions and examples, number of nodes, logarithmic height, number of leaf nodes, applications. | Algorithm Analysis 1 Problem Solving Space Complexity Time Complexity Classifying Functions by Their Asymptotic Growth Problem Solving: Main Steps Problem definition Algorithm design / Algorithm specification Algorithm analysis Implementation Testing Maintenance 2 1. Problem Definition What is the task to be accomplished? Calculate the average of the grades for a given student Find the largest number in a list What are the time /space performance requirements ? 3 2. Algorithm Design/Specifications Algorithm: Finite set of instructions that, if followed, accomplishes a particular task. Describe: in natural language / pseudo-code / diagrams / etc. Criteria to follow: Input: Zero or more quantities (externally produced) Output: One or more quantities Definiteness: Clarity, precision of each instruction Effectiveness: Each instruction has to be basic enough and feasible Finiteness: The algorithm has to stop after a finite (may be very large) number of steps 4 4,5,6: Implementation, Testing and Maintenance Implementation Decide on the programming language to use C, C++, Python, Java, Perl, etc. Write clean, well documented code Test, test, test Integrate feedback from users, fix bugs, ensure compatibility across different versions Maintenance 5 3. Algorithm Analysis Space complexity How much space is required Time complexity How much time does it take to run the algorithm 6 Space Complexity Space complexity = The amount of memory required by an algorithm to run to completion the most often encountered cause is “memory leaks” – the amount of memory required larger than the memory available on a given system Some algorithms may be more efficient if data completely loaded into memory Need to look also at system limitations . Classify 2GB of text in various categories – can I afford to load the entire collection? 7 Space Complexity (cont ) Fixed part: The size required to store certain data/variables, that is independent of the size of the problem: - . name of the . | Algorithm Analysis 1 Problem Solving Space Complexity Time Complexity Classifying Functions by Their Asymptotic Growth Problem Solving: Main Steps Problem definition Algorithm design / Algorithm specification Algorithm analysis Implementation Testing Maintenance 2 1. Problem Definition What is the task to be accomplished? Calculate the average of the grades for a given student Find the largest number in a list What are the time /space performance requirements ? 3 2. Algorithm Design/Specifications Algorithm: Finite set of instructions that, if followed, accomplishes a particular task. Describe: in natural language / pseudo-code / diagrams / etc. Criteria to follow: Input: Zero or more quantities (externally produced) Output: One or more quantities Definiteness: Clarity, precision of each instruction Effectiveness: Each instruction has to be basic enough and feasible Finiteness: The algorithm has to stop after a finite (may be very large) number of steps 4 4,5,6: Implementation, .