tailieunhanh - Lecture note Java methods A & AB: Object-oriented programming and data structures: Chapter 18 - Maria Litvin, Gary Litvin

Chapter 18: 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. | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Big-O Analysis of Algorithms 18- Theoretical details in this chapter are for mathematically-inclined students. This is AB-level 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 18- 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 18- 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, . | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Big-O Analysis of Algorithms 18- Theoretical details in this chapter are for mathematically-inclined students. This is AB-level 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 18- 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 18- 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 18- 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) 18- 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 18- Our main concern is time, but AP questions can also ask about space. .

• Kỹ thuật lập trình
• Java methods
• Object oriented programming
• Data structures
• Lập trình hướng đối tượng
• Cấu trúc dữ liệu
• Evaluation of algorithms
• Java syntax
• Lecture note Java methods
• Java collections framework
• Hardware terms
• Software development
• OO program models
• Describing algorithms
• Data types
• Boolean expressions
• Iterative statements
• Implementing classes
• String class
• Initializing arrays
• ArrayList pitfalls
• Binary search
• Binary files
• Computer graphics
• GUI components
• Mouse events