Learning Algorithms
豆瓣
George Heineman
简介
When it comes to writing efficient code, every software professional needs to have an effective working knowledge of algorithms. In this practical book, author George Heineman (Algorithms in a Nutshell) provides concise and informative descriptions of key algorithms that improve coding in multiple languages. Python software developers, testers, and maintainers will discover how algorithms solve computational problems creatively.
Each chapter builds on earlier chapters through eye-catching visuals and a steady rollout of key concepts, including an algorithm analysis to classify the performance of every algorithm presented in the book. At the end of each chapter, you'll get to apply what you've learned to a novel challenge problem--simulating the experience you might find in a technical code interview.
Examine fundamental algorithms central to computer science and software engineering
Learn common strategies for efficient problem solving--such as Divide and Conquer, Dynamic Programming, and Greedy Approaches
Analyze code to evaluate time complexity using big O notation
Use existing Python libraries to solve problems using algorithms
Understand the key steps in algorithms presented in the book
Use example code in your programs and documentation
目录
Table of contents
Preface
Who Is This Book For
About the Code
Acknowledgments
Conventions Used in This Book
Using Code Examples
O’Reilly Online Learning
How to Contact Us
1. Problem Solving
What Is an Algorithm?
Finding the Largest Value in an Arbitrary List
Counting Key Operations
Models Can Predict Algorithm Performance
Find Two Largest Values in an Arbitrary List
Tournament algorithm
Time Complexity and Space Complexity
Summary
Challenge Exercises
2. Analyzing Algorithms
Using Empirical Models to Predict Performance
Multiplication Can Be Faster
Performance Classes
Asymptotic Analysis
Counting All Operations
Counting All Bytes
When One Door Closes, Another One Opens
Binary Array Search
Almost as Easy as π
Two Birds with One Stone
Pulling It All Together
Curve Fitting Versus Lower and Upper Bounds
Summary
Challenge Exercises
3. Better Living Through Better Hashing
Associating Values with Keys
Hash Functions and Hash Codes
A Hashtable Structure for (Key, Value) Pairs
Detecting and Resolving Collisions with Linear Probing
Separate Chaining with Linked Lists
Removing an Entry from a Linked List
Evaluation
Growing Hashtables
Analyzing the Performance of Dynamic Hashtables
Perfect hashing
Iterate Over (Key, Value) Pairs
Summary
Challenge Exercises
4. Heaping It On
Max Binary Heaps
Inserting a (value, priority)
Removing the value with highest priority
Representing a Binary Heap in an Array
Implementation of Swim and Sink
Summary
Challenge Exercises
5. Sorting Without a Hat
Sorting by Swapping
Selection Sort
Anatomy of an O(N2) sorting algorithm
Analyze performance of Insertion Sort and Selection Sort
Recursion and Divide and Conquer
Merge Sort
Quicksort
Heap Sort
Performance Comparison Of O(N log N) Algorithms
Tim Sort
Summary
Challenge Exercises
6. Binary Trees: Infinity in the Palm of Your Hand
Getting Started
Binary Search Trees
Searching for Values in a Binary Search Tree
Removing Values from a Binary Search Tree
Traversing a Binary Tree
Analyzing Performance of Binary Search Tree
Self-Balancing Binary Trees
Analyzing Performance of Self-balancing Trees
Using Binary Tree as (Key, Value) Symbol Table
Using Binary Tree as Priority Queue
Summary
Challenge Exercises
7. Graphs: Only Connect!
Graphs Efficiently Store Useful Information
Using Depth First Search to Solve a Maze
Breadth First Search Offers Different Searching Strategy
Directed Graphs
Graphs with Edge Weights
Dijkstra’s Algorithm
All-Pairs Shortest Path
Floyd-Warshall Algorithm
Summary
Challenge Exercises
8. Wrapping It Up
Python Built-in Data Types
Implementing Stack in Python
Implementing Queues in Python
Heap and Priority Queue Implementations
Future Exploration
Index
