logo资料库

Algorithms Illuminated. Part 1. The Basics.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：5.80M 资料格式：pdf 举报 版权申诉
第1页 / 共217页
第2页 / 共217页
第3页 / 共217页
第4页 / 共217页
第5页 / 共217页
第6页 / 共217页
第7页 / 共217页
第8页 / 共217页
资料共217页，剩余部分请下载后查看
    Preface
    Introduction
    Why Study Algorithms?
    Integer Multiplication
    Karatsuba Multiplication
    MergeSort: The Algorithm
    MergeSort: The Analysis
    Guiding Principles for the Analysis of Algorithms
    Problems
    Asymptotic Notation
    The Gist
    Big-O Notation
    Two Basic Examples
    Big-Omega and Big-Theta Notation
    Additional Examples
    Problems
    Divide-and-Conquer Algorithms
    The Divide-and-Conquer Paradigm
    Counting Inversions in O(n logn) Time
    Strassen's Matrix Multiplication Algorithm
    An O(n logn)-Time Algorithm for the Closest Pair
    Problems
    The Master Method
    Integer Multiplication Revisited
    Formal Statement
    Six Examples
    Proof of the Master Method
    Problems
    QuickSort
    Overview
    Partitioning Around a Pivot Element
    The Importance of Good Pivots
    Randomized QuickSort
    Analysis of Randomized QuickSort
    Sorting Requires (n logn) Comparisons
    Problems
    Linear-Time Selection
    The RSelect Algorithm
    Analysis of RSelect
    The DSelect Algorithm
    Analysis of DSelect
    Problems
    Quick Review of Proofs By Induction
    A Template for Proofs by Induction
    Example: A Closed-Form Formula
    Example: The Size of a Complete Binary Tree
    Quick Review of Discrete Probability
    Sample Spaces
    Events
    Random Variables
    Expectation
    Linearity of Expectation
    Example: Load Balancing
    Index
    Algorithms Illuminated Part 1: The Basics Tim Roughgarden
    c 2017 by Tim Roughgarden All rights reserved. No portion of this book may be reproduced in any form without permission from the publisher, except as permitted by U. S. copyright law. Printed in the United States of America First Edition Cover image: Stanza, by Andrea Belag ISBN: 978-0-9992829-0-8 (Paperback) ISBN: 978-0-9992829-1-5 (ebook) Library of Congress Control Number: 2017914282 Soundlikeyourself Publishing, LLC San Francisco, CA tim.roughgarden@gmail.com www.algorithmsilluminated.org
    To Emma
    Contents Preface 1 Integer Multiplication Introduction 1.1 Why Study Algorithms? 1.2 1.3 Karatsuba Multiplication 1.4 MergeSort: The Algorithm 1.5 MergeSort: The Analysis 1.6 Guiding Principles for the Analysis of Algorithms Problems 2 Asymptotic Notation 2.1 The Gist 2.2 Big-O Notation 2.3 Two Basic Examples 2.4 Big-Omega and Big-Theta Notation 2.5 Additional Examples Problems 3 Divide-and-Conquer Algorithms 3.1 The Divide-and-Conquer Paradigm 3.2 Counting Inversions in O(n log n) Time 3.3 Strassen’s Matrix Multiplication Algorithm *3.4 An O(n log n)-Time Algorithm for the Closest Pair Problems 4 The Master Method Integer Multiplication Revisited 4.1 4.2 Formal Statement 4.3 Six Examples v vii 1 1 3 6 12 18 26 33 36 36 45 47 50 54 57 60 60 61 71 77 90 92 92 95 97
    vi Contents *4.4 Proof of the Master Method Problems 5 QuickSort 5.1 Overview 5.2 Partitioning Around a Pivot Element 5.3 The Importance of Good Pivots 5.4 Randomized QuickSort *5.5 Analysis of Randomized QuickSort *5.6 Sorting Requires ⌦(n log n) Comparisons Problems 6 Linear-Time Selection 6.1 The RSelect Algorithm *6.2 Analysis of RSelect *6.3 The DSelect Algorithm *6.4 Analysis of DSelect Problems A Quick Review of Proofs By Induction A.1 A Template for Proofs by Induction A.2 Example: A Closed-Form Formula A.3 Example: The Size of a Complete Binary Tree B Quick Review of Discrete Probability B.1 Sample Spaces B.2 Events B.3 Random Variables B.4 Expectation B.5 Linearity of Expectation B.6 Example: Load Balancing Index 103 114 117 117 121 128 132 135 145 151 155 155 163 167 172 180 183 183 184 185 186 186 187 189 190 192 195 199
    Preface This book is the first of a four-part series based on my online algorithms courses that have been running regularly since 2012, which in turn are based on an undergraduate course that I’ve taught many times at Stanford University. What We’ll Cover Algorithms Illuminated, Part 1 provides an introduction to and basic literacy in the following four topics. Asymptotic analysis and big-O notation. Asymptotic notation provides the basic vocabulary for discussing the design and analysis of algorithms. The key concept here is “big-O” notation, which is a modeling choice about the granularity with which we measure the running time of an algorithm. We’ll see that the sweet spot for clear high-level thinking about algorithm design is to ignore constant factors and lower-order terms, and to concentrate on how an algorithm’s performance scales with the size of the input. Divide-and-conquer algorithms and the master method. There’s no silver bullet in algorithm design, no single problem-solving method that cracks all computational problems. However, there are a few general algorithm design techniques that find successful ap- plication across a range of different domains. In this part of the series, we’ll cover the “divide-and-conquer” technique. The idea is to break a problem into smaller subproblems, solve the subproblems recursively, and then quickly combine their solutions into one for the original problem. We’ll see fast divide-and-conquer algorithms for sorting, integer and matrix multiplication, and a basic problem in computational geometry. We’ll also cover the master method, which is vii
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料