176x Filetype PDF File size 0.24 MB Source: www.cse.unsw.edu.au
Dynamic Programming Reminder: Algorithmic Complexity Dynamic Programming What is dynamic COMP4128 Programming Challenges programming? DPonatree Exponential DP DPwith Data Structures School of Computer Science and Engineering More example UNSWAustralia problems Table of Contents 2 Dynamic Programming 1 Reminder: Algorithmic Complexity Reminder: Algorithmic Complexity 2 What is dynamic programming? What is dynamic programming? DPonatree 3 DPonatree Exponential DP 4 Exponential DP DPwith Data Structures More example 5 DPwith Data Structures problems 6 More example problems Reminder: Algorithmic Complexity 3 Dynamic Programming The running time of your solution is important! Reminder: If you don’t think about the time complexity of your Algorithmic algorithm before coding it up, sooner or later you’ll end up Complexity What is wasting a lot of time on something something that’s too dynamic slow. programming? DPonatree This is especially tragic in exam environments. Exponential For simple code, analysing complexity can be as simple as DP multiplying together the bounds of nested for loops. DPwith Data Structures For recursive solutions, a rough bound is More example O(time spent in recursive function × problems recursion depth number of recursion branches ) For DP, it usually comes down to carefully determining the state space and cost of recursion. Reminder: Algorithmic Complexity 4 Dynamic Programming On most online judges (this applies to the problem sets), a Reminder: rough guideline is 50 million operations per second. Algorithmic Complexity Constant factors occasionally matter, e.g. if you have no What is recursion, or only tail-recursion, you might manage more dynamic programming? operations than this. DPonatree If you do float arithmetic, everything will be slow Exponential This means that for n ≤ 1,000,000, an O(nlogn) DP algorithm will probably run in time, but an O(n2) DPwith Data Structures algorithm will definitely time out. More example problems Best way to get a gauge of an online judge’s speed is to submit a simple for loop and compare the number of iterations it can do in 1 second to your local environment.
no reviews yet
Please Login to review.