tailieunhanh - Lecture Java methods: Object-oriented programming and data structures (3rd AP edition): Chapter 19 - Maria Litvin, Gary Litvin

Chapter 19 - Big-O analysis of algorithms. Theoretical details in this chapter are for mathematically-inclined students. This is AB-level material. This chapter also provides the necessary background for discussing data structures in the subsequent chapters. | Big-O Analysis of Algorithms Copyright © 2015 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 3rd AP edition 19- Theoretical details in this chapter are for mathematically-inclined students. This is not AP CS material. Objectives: Learn the big-O definition and notation Review big-O for some common tasks and algorithms studied earlier Review several popular sorting algorithms and their average, best, and worst case big-O 19- This chapter also provides the necessary background for discussing data structures in the subsequent chapters. Evaluation of Algorithms Practice: benchmarks Theory: asymptotic analysis, big-O t n 19- The first impression may be that benchmarks leave no room for theory. This is not so. Analysis of Algorithms — Assumptions Abstract computer model with “unlimited” RAM Unlimited range for integers Basic operations on integers (addition, . | Big-O Analysis of Algorithms Copyright © 2015 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 3rd AP edition 19- Theoretical details in this chapter are for mathematically-inclined students. This is not AP CS material. Objectives: Learn the big-O definition and notation Review big-O for some common tasks and algorithms studied earlier Review several popular sorting algorithms and their average, best, and worst case big-O 19- This chapter also provides the necessary background for discussing data structures in the subsequent chapters. Evaluation of Algorithms Practice: benchmarks Theory: asymptotic analysis, big-O t n 19- The first impression may be that benchmarks leave no room for theory. This is not so. Analysis of Algorithms — Assumptions Abstract computer model with “unlimited” RAM Unlimited range for integers Basic operations on integers (addition, multiplication, etc.) take fixed time regardless of the values of the operands 19- This model of an abstract machine is not realistic, but it is useful. There is another model based on operations on individual bits, which is more realistic, but harder to use. Big-O Analysis Studies space and time requirements in terms of the “size” of the task The concept of “size” is somewhat informal here: The size of a list or another collection The dimensions of a 2-D array The argument of a function, for example, factorial(n) or fibonacci(n) The number of objects involved (for example, n disks in the Tower of Hanoi puzzle) 19- In the model based on bits, the size of the task is simply the number of bits necessary to represent the input data. Big-O Assumptions Here our main concern is time Ignores a constant factor measures the time in terms of the number of some abstract steps Applies to large n, studies asymptotic behavior 19- So the time is measured in abstract units or steps, not .