Lecture 5-6

[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

1. So P2 is a NP problem.
2. P1 is a NP complete, all other problems R in NP can be polynomially reduced to P1.
3. 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.