关于算法:cs61b-week7-Asymptotics-I

1. 问题引入

从本周起正式进入 cs61b 的后半局部课程，数据结构，思考一个问题:

现有一个有序数组，查找数组中是否有反复项

算法 1: 逐项比拟，比方 A[0]别离与 A[1],A[2],A[3]……A[n]比拟，之后再从 A[1]开始，与 A[2],A[3]….A[n]比拟，A[2]与 A[3],A[4]…. 比拟，以此类推。

显然算法 1 并未充分利用数组有序性的特点，因而算法 2:
因为数组是有序的，因而咱们只须要比拟相邻两项即可，反复的元素肯定位于相邻两项。
即 A[0]与 A[1]比拟,A[1]与 A[2]比拟，A[2]与 A[3]比拟 ….A[n-1]与 A[n]比拟。

应用 Java 实现以上两种算法，别离是

// 算法 1
public static boolean dup1(int[] A) {for (int i = 0; i < A.length; i += 1) {for (int j = i + 1; j < A.length; j += 1) {if (A[i] == A[j]) {return true;}
    }
  }
  return false;
}

// 算法 2
public static boolean dup2(int[] A) {for (int i = 0; i < A.length - 1; i += 1) {if (A[i] == A[i + 1]) {return true;}
  }
  return false;
}

那么当初的问题是: 算法 1 与算法 2 哪个更好？判断规范是什么？

2. 运行工夫测量

在 Linux 下应用命令 time 可实现程序运行工夫的测量。咱们的 main() 函数次要是别离对 dup1()和 dup2()调用:

public static void main(String[] args) {int N = Integer.parseInt(args[0]);
  int[] A = makeArray(N);
  dup1(A); // dup2(A);
}

上图是 dup1()，下图是 dup2(), 当数组大小为 200000 时，比照运行工夫可知 dup2()显著快很多，
当数组大小为 1000000 时，dup1()间接 TLE 了，dup2()仍然能够很快得出后果

然而事实上仅凭运行工夫得出的后果只是给人一种直观的感触，算法 2 更快，工夫测量的办法必须基于同一台机器上，不同的电脑性能不同，运行工夫也会不同，构想一下在超级计算机上运行 dup1()，仍然能够绝对较快。

3. 掂量计算成本

当初咱们思考以一种新的形式来掂量两种算法的运行工夫，即分析程序的每一条代码操作的执行次数，为何这样思考更优？是因为无论在哪台机器上运行这两个函数 dup1()与 dup2()，其代码执行次数是肯定的，与机器性能优劣无关，更加迷信。
算法 1

算法 2

显然，线性函数与抛物线相比，前者更优，以上执行次数公式是 josh 间接给出的，后续会有具体
介绍。

4. 简化老本模型

事实上，在剖析一个程序的计算成本时，不用思考如此粗疏，可做以下简化:

Simplifications:

• 只思考最坏状况
• 抉择最具代表性的操作
• 疏忽低阶函数和常数系数

算法解决规模非常重要！最坏的状况往往最具备代表性，当程序的工作处理量很少时，在古代计算机上，一秒可能执行 1e8 的任务量，此时无论你抉择哪种算法都影响不大，然而当任务量极大时，算法的优劣则体现进去了，好的算法可能疾速执行完程序并反馈给用户，而劣式算法会破费数以千计的工夫。

让咱们从新对 dup1()进行预计:

1. 选取最具代表性的操作，例如:
2. 增量 +=1(其实并非最具代表性) 代码执行次数是 1 to \((N^2+N)/2 \)
3. 思考最坏状况: \((N^2+N)/2 \)
4. 疏忽常数系数与低阶函数: \(N^2 \)

因而最坏状况下的运行工夫阶数为 \(N^2 \)

5. 准确得出代码执行次数

下面咱们是间接给出的操作的执行次数，可能初学者不太了解如何得出，因而这次咱们准确地给出数学公式的表白。

选取最具代表性操作:

$$
if (A[i] == A[j])
$$

即 == 操作，再一次对 dup1()进行预计，能够别离列出 i 与 j 的取值方阵，寻找法则(也能够依据代码间接剖析进去，如 i = 0, j = 1,2,……N-1)

几何直观预计

在几何直观上，== 的操作次数即 蓝色区域三角形 的面积: \(N^2/2\)

6.Big-Theta

定义:

$$
R(n)\in \Theta(f(n))
$$

示意存在两个数 \(k_{1},k_{2}\), 对所有 \(N > N_{0}\) , 有:

$$
k_{1}\cdot f(n) \le R(n) \le k_{2}\cdot f(n)
$$

即 \(\Theta(f(N))\)的含意是 \(R(N)\)属于 \(f(N)\)的函数簇

Example:
\(40 sin(N) + 4N^2 ∈ Θ(N^2) \)
\(R(N) = 40 sin(N) + 4N^2 \)
\(f(N) = N^2 \)

k1 = 3
k2 = 5

7.Big-O

定义:

$$
R(n)\in O(f(n))
$$

示意存在 \(k_{2}\), 对所有 \(N > N_{0}\) , 有:

$$
R(n) \le k_{2}\cdot f(n)
$$

即 \(O(f(N))\)的含意是 \(k_{2} \cdot f(N)\)是 \(R(N)\)上界

Example:
\(40 sin(N) + 4N^2 ∈ O(N^4) \)
\(R(N) = 40 sin(N) + 4N^2 \)
\(f(N) = N^4 \)

k2 = 1

8. 总结