Performance Measure of Algorithms(1)--Mathematical Background

时间复杂度与空间复杂度请访问Performance Measure of Algorithms(2)–Space Complexity & Time Complexity
递归算法的时间复杂度分析请访问Performance Measure of Algorithms(3)–递归算法的时间复杂度分析

通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二就是是算法性能分析。经常分析的是算法的时间复杂度和空间复杂度，算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。

1. What do we measure?

Correctness 正确性
Readability 可读性
Robustness 健壮性
Usability 可用性
simplicity 简单性
efficiency 效率※

2. Three complementary methods

Empirical实证: use real-world data with an implemented system.
Simulation模拟: use simulated data with an implemented system or with a model system
Analytical分析: use theoretic-model data with a theoretic-model system

3. Machine-independent time

算法的性能有时取决于我们计算机的运行速度，So how to measure the performance of algorithms ?
BIG IDEA:
• Ignore machine-dependent constants.
• Look at growth of T(n) as n → ∞ “Asymptotic Analysis” （渐近分析）

RAM (Random Access Machine) Model

Algorithms can be measured in a machine-independent way using the Random Access Machine (RAM) model. This model assumes a single processor. In the RAM model, instructions are executed one after the other, with no concurrent operations. This model of computation is an abstraction that allows us to compare algorithms on the basis of performance. The assumptions made in the RAM model to accomplish this are:
• Each simple operation takes 1 time step.
• Loops and subroutines are not simple operations.
• Each memory access takes one time step, and there is no shortage of memory.
For any given problem the running time of an algorithms is assumed to be the number of time steps. The space used by an algorithm is assumed to be the number of RAM memory cells.

4. Which algorithm is the fastest?

Consider a problem that can be solved by 5 algorithms, A1, A2, A3, A4, A5 using different number of operations (time complexity):

Algorithm A1 requires f1(n) operations on an input of size n, A2 requires f2(n) operations etc.
Which algorithm will be fastest？This will depend upon the size of the input n as we will now see..

5. Mathematical Background

5.1 Relative rates of growth

(1) T(N) = O(f(N))

(2) T(N) = Ω(g(N))

(3) T(N) = Θ(b(N))
If and only if T(N) = O(b(N)) and T(N) = Ω(b(N))

(4) T(N) = o(p(N))
If T(N) = O(p(N)) and T(N) ≠ Θ(p(N))

5.2 Polynomial functions & Exponential functions

图像如下：

Typical Growth Rates：

5.3 Some Rules

Rule 1

Examples:
if T1(N) = O(N2) and T2(N)= O(N) then
(a) T1(N) + T2(N) = O(N2) T1(N) + T2(N) = O(N的3次方也是对的)
(b) T1(N) * T2(N) = O(N3)

O(g1(n)) ∗ O(g2(n)) → O(g1(n) ∗ g2(n))
Ω(g1(n)) ∗ Ω(g2(n)) → Ω(g1(n) ∗ g2(n))
Θ(g1(n)) ∗ Θ(g2(n)) → Θ(g1(n) ∗ g2(n))

Rule 2

Rule 3

证明如下：

Rule 4

Inside a Big-Oh, ignored: Low-order terms and Constants（常数和低次项忽略）
O(c · g(n)) → O(g(n))
Ω(c · g(n)) → Ω(g(n))
Θ(c · g(n)) → Θ(g(n)),

5.4 Proof