关于算法: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.总结