Estrutura de dados - livro do shaffer

121958 palavras 488 páginas
Data Structures and Algorithm
Analysis
Edition 3.2 (C++ Version)
Clifford A. Shaffer
Department of Computer Science
Virginia Tech
Blacksburg, VA 24061
November 19, 2012
Update 3.2.0.7
For a list of changes, see http://people.cs.vt.edu/˜shaffer/Book/errata.html Copyright © 2009-2012 by Clifford A. Shaffer.
This document is made freely available in PDF form for educational and other non-commercial use. You may make copies of this file and redistribute in electronic form without charge. You may extract portions of this document provided that the front page, including the title, author, and this notice are included. Any commercial use of this document requires the written consent of the author. The author can be reached at shaffer@cs.vt.edu. If you wish to have a printed version of this document, print copies are published by Dover Publications
(see http://store.doverpublications.com/048648582x.html).
Further information about this text is available at http://people.cs.vt.edu/˜shaffer/Book/. Contents

Preface

xiii

I

Preliminaries

1

1

Data Structures and Algorithms
1.1 A Philosophy of Data Structures
1.1.1 The Need for Data Structures
1.1.2 Costs and Benefits
1.2 Abstract Data Types and Data Structures
1.3 Design Patterns
1.3.1 Flyweight
1.3.2 Visitor
1.3.3 Composite
1.3.4 Strategy
1.4 Problems, Algorithms, and Programs
1.5 Further Reading
1.6 Exercises

3
4
4
6
8
12
13
13
14
15
16
18
20

2

Mathematical Preliminaries
2.1 Sets and Relations
2.2 Miscellaneous Notation
2.3 Logarithms
2.4 Summations and Recurrences
2.5 Recursion
2.6 Mathematical Proof Techniques

25
25
29
31
32
36
38 iii iv

Contents

2.7
2.8
2.9
3

II
4

2.6.1 Direct Proof
2.6.2 Proof by Contradiction
2.6.3 Proof by Mathematical Induction
Estimation
Further Reading
Exercises

Algorithm Analysis
3.1 Introduction
3.2 Best, Worst, and Average Cases
3.3 A Faster Computer, or a Faster Algorithm?

Relacionados

  • o desenvolvimento humano
    5621 palavras | 23 páginas
  • Didatica analise
    698 palavras | 3 páginas
  • Identificação dos problemas conceituais dos circuitos elétricos simples em alunos de engenharia elétrica
    4895 palavras | 20 páginas
  • violencia sexual contra crianças e adolescentes
    8843 palavras | 36 páginas
  • Capital humano
    6936 palavras | 28 páginas
  • Pesquisa em educação em ciências
    4836 palavras | 20 páginas
  • aprendizagem
    4381 palavras | 18 páginas
  • Análise da postura de um professor frente ao ambiente de aprendizagem
    4998 palavras | 20 páginas
  • Relatório de estágio supervisionado observação
    4044 palavras | 17 páginas
  • Resumo educaçaõ física
    4109 palavras | 17 páginas