數(shù)據(jù)結(jié)構(gòu)與算法分析

前言

This book describes data structures, methods of organizing large amounts of data,and algorithm analysis, the estimation of the running time of algorithms. As com-puters become faster and faster, the need for programs that can handle large amountsof input becomes more acute. Paradoxically, this requires more careful attention toefficiency, since inefficiencies in programs become most obvious when input sizes arelarge. By analyzing an algorithm before it is actually coded, students can decide if aparticular solution will be feasible. For example, in this text students look at specificproblems and see how careful implementations can reduce the time constraint forlarge amounts of data from 16 years to less than a second. Therefore, no algorithmor data structure is presented without an explanation of its running time. In somecases, minute details that affect the running time of the implementation are explored.Once a solution method is determined, a program must still be written. Ascomputers have become more powerful, the problems they must solve have becomelarger and more complex, requiring development of more intricate programs. Thegoal of this text is to teach students good programming and algorithm analysis skillssimultaneously so that they can develop such programs with the maximum amountof efficiency.This book is suitable for either an advanced data structures （CS7） course ora first-year graduate course in algorithm analysis. Students should have some know-ledge of intermediate programming, including such topics as pointers and recursion,and some background in discrete math.

內(nèi)容概要

本書曾被評(píng)為20世紀(jì)頂尖的30部計(jì)算機(jī)著作之一，作者在數(shù)據(jù)結(jié)構(gòu)和算法分析方面卓有建樹，他的數(shù)據(jù)結(jié)構(gòu)和算法分析的著作尤其暢銷，并受到廣泛好評(píng)，已被世界500余所大學(xué)選作教材。        在本書中，作者精煉并強(qiáng)化了他對(duì)算法和數(shù)據(jù)結(jié)構(gòu)方面創(chuàng)新的處理方法。通過C程序的實(shí)現(xiàn)，著重闡述了抽象數(shù)據(jù)類型的概念，并對(duì)算法的效率、性能和運(yùn)行時(shí)間進(jìn)行了分析?！　≈赜懻摿怂惴ㄔO(shè)計(jì)技巧。包括貪婪算法、分治算法、動(dòng)態(tài)規(guī)劃、隨機(jī)化算法以及回溯算法。系統(tǒng)介紹了當(dāng)前流行的論題和新的數(shù)據(jù)結(jié)構(gòu)，如斐波那契堆、斜堆、二項(xiàng)隊(duì)列、跳躍表和伸展樹。詳細(xì)討論了攤還分析，考查書中介紹的一些高級(jí)數(shù)據(jù)結(jié)構(gòu)?！　≡黾恿烁呒?jí)數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的內(nèi)容，包括紅黑樹、自頂向下伸展樹、treap樹、k-d樹、配對(duì)堆等。整合了堆排序平均情況分析的一些新結(jié)果。

作者簡(jiǎn)介

Mark Allen Weiss 1987年在普林斯頓大學(xué)獲得計(jì)算機(jī)科學(xué)博士學(xué)位。師 從Roberl Sedgewick，現(xiàn)任美國(guó)佛羅里達(dá)國(guó)際大學(xué)計(jì)算與信息科學(xué)學(xué)院教授。他曾擔(dān)任全美AP(Advanced Placement)考試計(jì)算機(jī)學(xué)科委員會(huì)主席。其主要研究方向是數(shù)據(jù)結(jié)構(gòu)、算法和教育學(xué)。

書籍目錄

1　Introduction　1.1.  What's the Book About?　1.2.  Mathematics Review　　1.2.1.  Exponents　　1.2.2.  Logarithms　　1.2.3.  Series　　1.2.4.  Modular Arithmetic　　1.2.5.  The P Word　1.3.  A Brief Introduction to Recursion　　Summary　　Exercises　　References2　Algorithm Analysis　2.1.  Mathematical Background　2.2.  Model　2.3. What to Analyze　2.4.  Running Time Calculations　　2.4.1. A Simple Example　　2.4.2.  General Rules 　　2.4.3.  Solutions for the Maximum Subsequence Sum Problem　　2.4.4.  Logarithms in the Running Time　　2.4.5.  Checking Your Analysis　　2.4.6. A Grain of Salt　　Summary　　Exercises　　References……

章節(jié)摘錄

插圖：This example illustrates what we call randomized algorithms. At least onceduring the algorithm, a random number is used to make a decision. The runningtime of the algorithm depends not only on the particular input, but also on therandom numbers that occur.The worst-case running time of a randomized algorithm is almost always thesame as the worst-case running time of the nonrandomized algorithm. The importantdifference is that a good randomized algorithm has no bad inputs, but only badrandom numbers （relative to the particular input）. This may seem like only aphilosophical difference, but actually it is quite important, as the following exampleshows.Consider two variants of quicksort. Variant A uses the first element as pivot,while variant B uses a randomly chosen element as pivot. In both cases, the worst-case running time is （N2）, because it is possible at each step that the largestelement is chosen as pivot. The difference between these worst cases is that there is aparticular input that can always be presented to variant A to cause the bad runningtime. Variant A will run in （N2） time every single time it is given an already-sortedlist. If variant B is presented with the same input twice, it will have two differentrunning times, depending on what random numbers occur.

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)與算法分析:C語言描述》：經(jīng)典原版書庫

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    數(shù)據(jù)結(jié)構(gòu)與算法分析 PDF格式下載

---