1. Scientific method of analyzing algorithm:
a) Observe some feature of the natural world.
b) Hypothesize a model that is consistent with the observations.
c) Predict events using the hypothesis.
d) Verify the predictions by making further observations.
e) Validate by repeating until the hypothesis and observations agree.
2. Knuth prooves that in principle, accurate mathematical models of algorithm analysis are available. Total running time is the sum of cost × frequency for all operations.
3. Turing mentioned that we can use some basic operation (most common operation in the algorithm) as a proxy for running time.
4. Tilde notation : Estimate running time (or memory) as a function of input size N. Ignore lower order terms:
– when N is large, terms are negligible
– when N is small, we don't care
Technical definition. f(N) ~ g(N) means lim N→ ∞ f (N)/g(N) = 1
5. the small set of functions:
1, log N, N, N log N, N^2, N^3, and 2^N
suffices to describe order-of-growth of typical algorithms.
6. An N^2 log N algorithm for 3-SUM problem ( given a list of numbers , try to tell how many triples' sum equals to 0. )
Sorting-based algorithm.
a) Sort the N (distinct) numbers.
b) For each pair of numbers a[i] and a[j], binary search for -(a[i] + a[j]).
Analysis. Order of growth is N^2 log N.
a) Step 1: N^2 with insertion sort.
b) Step 2: N^2 log N with binary search.
7. Commonly-used notations in the theory of algorithms:
8. Algorithm design approach:
Start:
a) Develop an algorithm.
b) Prove a lower bound.
Gap?
a) Lower the upper bound (discover a new algorithm).
b) Raise the lower bound (more difficult).
9. Tilde-notation provide an approximate model of algorithm analysis.
10. Typical memory usage for objects in Java:
Object overhead: 16 bytes.
Reference: 8 bytes.
Padding: Each object uses a multiple of 8 bytes.
11. A String of length N
typically uses 40 bytes (for the String
object) plus 24 + 2N
bytes (for the array that contains the characters) for a total of 64 + 2N
bytes.
12. Total memory usage for a data type value:
a) Primitive type: 4 bytes for int, 8 bytes for double, …
b) Object reference: 8 bytes.
c) Array: 24 bytes ( 16 bytes of object overhead, 4 bytes for the length, and 4 bytes of padding) + memory for each array entry.
d) Object: 16 bytes + memory for each instance variable + 8 bytes if inner class (for pointer to enclosing class).
e) Padding: round up to multiple of 8 bytes.
- 大小: 87 KB
- 大小: 59.6 KB
- 大小: 49.7 KB
分享到:
相关推荐
Based on a new classification of algorithm design techniques and a clear delineation of analysis methods, Introduction to the Design and Analysis of Algorithms presents the subject in a coherent and ...
根据提供的文件信息,我们可以深入探讨《算法分析导论》这一主题。这本由Robert Sedgewick和Philippe Flajolet合著的书籍是算法分析领域的一部经典之作,旨在为读者提供全面且深入的算法分析知识。...
An Introduction to the Analysis of Algorithms(2nd) 英文无水印pdf 第2版 pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自...
Introduction to the Design and Analysis of Algorithms 3rd Edition (算法分析设计基础Anany Levitin )第三版课后答案,第三版,1-12章全,有hints也有solutions,英文版
1. 算法设计与分析(The Design and Analysis of Algorithms):文档标题强调了算法设计与分析的重要性。算法作为解决问题的一系列定义良好的指令集,在计算机科学中扮演着核心的角色。设计算法要求既高效又能准确...
Introduction to the Design and Analysis of Algorithms的中文版3
Anany Levitin的Introduction to the Design and Analysis of Algorithms中文版1
Title: The Design and Analysis of Algorithms Author: A. Levitin ISBN: 0-321-35828-7 Publisher: Addison Wesley Pub. Date: 2nd Ed., 2007 算法设计与分析基础 中文版 教材
An introduction to the Analysis of Algorithms, Robert Sedgewick 著
Introduction to the Design and Analysis of Algorithms 算法分析与设计基础 官方答案 适用于本书第二版 不是有些复制,粘贴到word里的答案,包含题目tips和详细分析 仅限1-10章
Introduction to the Design and Analysis of Algorithms 3rd Edition (算法分析设计基础Anany Levitin )第三版课后答案,第三版,1-12章全,有hints也有solutions,英文版
《算法设计与分析导论》第三版是一本深入探讨算法设计与分析的权威教材,它不仅涵盖了算法的基本概念,还详细介绍了多种算法的设计方法及其在实际问题中的应用。本书通过丰富的示例和详尽的解释,帮助读者理解并掌握...
本书基于“Introduction to the Design and Analysis of Algorithms”第二版的内容,旨在帮助读者解决书中提出的练习题,深化对算法设计与分析的理解。 在算法的世界里,设计是创造解决问题的步骤,而分析则是评估...
《算法设计与分析》是计算机科学领域中至关重要的一门学科,它主要研究如何有效地解决问题,并对解决方案进行评估和优化。这门学科的核心在于理解和利用算法,以提高计算效率,节省资源,解决复杂问题。...
关于算法分析的数学知识的一本书,内容跟《具体数学》那本书可能有点重复,但是难度似乎更大一点,虽然内容没那么多,更精简一些。
本书十分适合作为算法设计和分析的基础教材,也适合任何有兴趣探究算法奥秘的读者使用,只要读者具备数据结构和离散数学的知识。
**标题**:“Introduction to the Design and Analysis of Algorithms 3rd edition.pdf” **描述**:“Introduction to the Design and Analysis of Algorithms 3rd edition.pdf” 该书籍主要介绍了算法设计与分析...
### 算法设计与分析Design and Analysis of Algorithms #### 一、基础知识与技术 **1.1 分治法(Divide-and-Conquer)** 分治法是一种将问题分解为若干个规模较小的子问题来解决的方法。这些子问题相互独立且与原...