[toc]
Lecture 5-6
P2.What is complexity analysis?
什么是算法复杂度
- The complexity of an algorithm is the amount of resources it needs in order to execute.
- Time complexity - Amount of time the algorithm needs
- Space complexity - Amount of memory the algorithm needs
P4-5.Basic operations of an algorithm & What is a basic operation?
- 不同算法的Basic operation是什么。排序中的遍历过程、merge比较
- A basic operation can be seen as an operation that is fundamental for the performance of a particular algorithm.
- The performance of the algorithm is in principle proportional(成正比) to the number of basic operations.
不同算法的Basic operation是什么
- In sorting algorithms: comparing two elements
- Graph traversal: traversing an edge
- For some algorithms a basic operation can be a whole loop, including all operations inside the loop
P7.Complexity as a function of the input - Examples
-
常见算法的复杂度、最好的情况、最坏的情况、在什么情况下最好
时间复杂度.png
- 当已经排好序的情况下最好
P20.Average and Worst case analysis
- 掌握最坏的情况、不用掌握平均的
- The worst-case complexity W(n) of an algorithm is the maximum number of basic operations performed for any input of n.
- The average-case complexity A(n) of an algorithm is the average number of basic operations performed by the algorithm, where each input I occurs with some probability p(I).
P23.Relative growth rate of functions
- 给出一个表达式，可以用Big O的形式表达出来、去掉常数项和低次项还有系数
P29.Example: )
,)
, and )
- 上下界、O的上界、Ω的下界、Θ的确界
-
各个界的概念无需记住
各个界.jpg
-
例子
example.jpg 考点
给出一个表达式，可以用Big O的形式表达出来、去掉常数项和低次项还有系数
P36.P and NP
- NP中N 的含义、NP是否等于P、一般是不等、说明原因。 证明一个问题是NP问题，写出步骤。P与NP的关系（目前认为两者不等，如果P与NP相等会怎么样,那么所有的问题都是可解的）
- P is the class of problems that can be solved by plynomial bound algorithms.
-
NP（non-deterministic polynomial-time） is more complicated to describe.
◮ It contains problems that we believe are more difficult to solve
than those in P.
◮ We believe that they cannot be solved using any polynomial
bound algorithm.
◮ However, we do not know whether this is true or not.
证明一个问题是NP问题，写出步骤。
P44. NP-complete
什么是NP-complete
- 所有的P问题都可以归约到它。All problems in NP can be reduced to it.
如何证明一个问题(P2)是NP-complete
- So P2 is a NP problem.
- P1 is a NP complete, all other problems R in NP can be polynomially reduced to P1.
- Show P1 can be polynomially reduced to P2
P46.How to show that a problem is N P complete I
- 过于具体、可以简化
P47.How to show that a problem is N P complete II
- 具体证明步骤、会证明
- 把第二条分成两点
P48.Amortized analysis - Initial example
- 只需要掌握基本概念、 a sequence of operations是关键词
- Amortized analysis is a technique for analyzing the running time of repeated operations on a data structure.
The cost for a single insert might be much worse than the amortized analysis. 单次的操作开销可能会比均摊分析的时间复杂度高，因为均摊分析计算的是平均的时间复杂度
It is used when one is interested in calculating a worst-case average bound per operation for any sequence of operations
It does not say anything about the cost of a specific operation in the sequence.
It is particular useful in situations where there are few expensive (slow) operations that are compensated by many inexpensive (fast)operations.
P52.Amortized or worst-case analysis
- In applications where it is important that all operations have a low cost, it might be more appropriate to use a worst-case analysis than an amortized analysis.
P53.Amortized vs average-case analysis
- 两者并不一样、AC是发生的概率，并不考虑多个步骤再平均
Amortized analysis provides an upper bound on the average cost per operation whereas average-case analysis provides an average cost per iteration, where consideration is taken to the probability of the occurrence of dierent inputs.
Amortized analysis provides an upper bound on the running time of a sequence of operations. Average-case analysis provides no such bound.
Amortized analysis needs no information about the probability on inputs.
