部分题目

01-简介

Task 1

• 根据power2()，设计一个算法，在 O(logn)时间内计算出fib(n)。其中，power2()方法是用来求幂函数$2^n$，实现如下：

  //power2
  long long sqr ( long long a ) { return a * a; } //平方：若是连续执行，很快就会数值溢出！
  long long power2 ( int n ) { //幂函数2^n算法（优化递归版），n >= 0
      if ( 0 == n ) return 1; //递归基；否则，视n的奇偶分别递归
      return ( n & 1 ) ? sqr ( power2 ( n >> 1 ) ) << 1 : sqr ( power2 ( n >> 1 ) );
  } //O(logn) = O(r)，r为输入指数n的比特位数

  解：由于斐波那契数列可以使用矩阵乘法来求值：

  $$\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)\cdot \left(\begin{array}{c}fib(n-1)\\ fib(n)\end{array}\right)=\left(\begin{array}{c}fib(n)\\ fib(n+1)\end{array}\right)$$

  则可以得到如下公式：

  $$\left(\begin{array}{c}fib(n)\\ fib(n+1)\end{array}\right)={\left(\begin{array}{ll}0& 1\\ 1& 1\end{array}\right)}^n\left(\begin{array}{l}fib(0)\\ fib(1)\end{array}\right)={\left(\begin{array}{ll}0& 1\\ 1& 1\end{array}\right)}^n\left(\begin{array}{l}0\\ 1\end{array}\right)$$

  而矩阵乘法的时间复杂度为常数时间。则总的时间复杂度为$O(\log n)$。

Task 2

• 对中华更相减损术算法的分析：

  long long gcdCN ( long long a, long long b ) { //assert: 0 < min(a, b)
      int r = 0; //a和b的2^r形式的公因子
      while ( ! ( ( a & 1 ) || ( b & 1 ) ) ) { //若a和b都是偶数
          a >>= 1; b >>= 1; r ++; //则同时除2（右移），并累加至r
      } //以下，a和b至多其一为偶
      while ( 1 ) {
          while ( ! ( a & 1 ) ) a >>= 1; //若a偶（b奇），则剔除a的所有因子2
          while ( ! ( b & 1 ) ) b >>= 1; //若b偶（a奇），则剔除b的所有因子2
          ( a > b ) ? a = a - b : b = b - a; //简化为：gcd(max(a, b) - min(a, b), min(a, b))
          if ( 0 == a ) return b << r; //简化至平凡情况：gcd(0, b) = b
          if ( 0 == b ) return a << r; //简化至平凡情况：gcd(a, 0) = a
      }
  }

  1. 该算法的渐进时间复杂度$O(\log (a+b))$，与欧几里得算法相同。
  2. 考查该算法的每一步迭代，紧接于两个内部while循环之后设置一个断点，观察此时的a和b。实际上，在a和b各自剔除了所有因子2之后，此时它们都将是奇数。接下来，无论二者大小如何，再经一次互减运算，它们必然将成为一奇一偶。比如，不失一般性，设$a>b$，则得到：$(a-b)$偶数，$b$奇数；再经一步迭代并重新回到断点时，前者至多是：$(a-b)/2$，两个变量之和至多是$(a-b)/2+b\le (a+b)/2$。可见，每经过一步迭代，$a+b$减少一半，故总体迭代步数不超过：${\log }_2(a+b)$。
  3. 并且，相较于欧几里得算法而言，该算法涉及的运算更为简单，只有加减和移位操作，而没有欧几里得算法中的乘除操作。

Task 3

• 设计一个就地移位的算法，使得有$n$个元素的数组arr[]进行平移操作，让第$k$项$(k\le n-1)$至数组的首位，让第$k-1$项至数组的末位。

  int shift2 ( int* A, int n, int k ) { //倚劣倒置算法，将数组循环左秱k位，O(3n) 
      k %= n; //确保k <= n 
      reverse ( A, k ); //将匙间A[0, k)倒置：O(3k/2)次操作 
      reverse ( A + k, n - k ); //将匙间A[k, n)倒置：O(3(n - k)/2)次操作 
      reverse ( A, n ); //倒置整个数组A[0, n)：O(3n/2)次操作 
      return 3 * n; //迒回累计操作次数，以便不其它算法比较：3/2 * (k + (n - k) + n) = 3n 
  }//逻辑十分巧妙

  原理：若在原向量$V$中前$k$个元素组成的前缀为$L$，剩余的（后缀）部分为$R$，经整体左移之后的向量应为$R+L$；这里约定，任意向量$V$整体倒置后的结果记作$V^{\prime }$。于是该算法的原理来自如下恒等式：

  $$R+L=(L^{\prime }+R^{\prime }{)}^{\prime }$$

Task 4

对于某些算法的时间复杂度分析：

• Subtask 1:

  void F(int n) { 
  for (int i = 0; i < n; i ++) 
     for (int j = 1; j < n; j <<= 1); 
  }

  复杂度：

  $$\sum _{i=0}^{n-1}\sum _{(k=\log j)=0}^{\log n-1}1=\sum _{i=0}^{n-1}(\log n-1)=n\log n-n=O(n\log n)$$

• Subtask 2:

  void F(int n){
      for(int i=1,r=1; i<n; i<<=r,r<<=1);
  }

  复杂度：$i\to i\cdot 2^r,r\to 2^r$。所以，有$i=\prod _{t=0}^{k-1}{2}^{2^t}=2^{2^k-1}$, $i<n\Rightarrow 2^k-1\le \log n\Rightarrow k\le \log \log n$.

• Subtask 3:

  void F(int n){
  	for(int i=1;i<n;i=1<<i)
  }

  即每经一次迭代，$i$即增长至$2^i$。设经过$k$次迭代之后，因$i\ge n$而退出迭代。现颠倒原迭代的方向，其过程应等效于反复令$n={\log }_{2}n$，并经k次迭代之后有$n\le 1$。由此可知，若对$n$反复取对数直至其不大于1，则$k$等于其间所做对数运算的次数，记作$k={\log }^{\ast }n$， 读作“log-星-n”。

  所以时间复杂度为$O({\log }^{\ast }n)$.

  $O(\log \log n)$和$O({\log }^{\ast }n)$均可视作常数。特别地，对于$n=2^{270}$，有${\log }^{\ast }n<5$。

• Subtask 4:

  int sum( int A[], int n ) 
  {  
  	return  n < 1  ?  0 : sum(A, n - 1) + A[n - 1];  
  }

  时间复杂度：

  由于单个递归实例需要$O(1)$时间完成，共有$n$个实例，所以整个算法的复杂度是$O(n)$。当sum(A,n)调用sum(A,n-1)时，sum(A,n)函数中的数据以“函数帧”的形式被压入一个栈中，并没有处于执行状态。

Task 5

下列函数渐进增长的大小排序：

$$O\left(\frac{n}{\log n}\right)>O(n^{\frac{2}{3}})>O({\log }^{2}n)>O(\log \log n)$$

因为，对数函数$\log n$的渐进增长要慢于任何次数的幂函数$O(x^{\epsilon }),\epsilon >0$。

02-向量

Task 1

12-图基础

Task 1

在一个含有$n$个顶点的简单无向图中，边的数量最多为${\displaystyle \frac{n(n-1)}{2}}$，此时度最小的顶点的度为$n-1$。

因为每个顶点都可以与其他$n-1$个顶点连接一条边，但这样会计算两次每条边（因为无向图的边是双向的），所以需要除以$2$。此时，每个点的度数相同，都是$n-1$。

Task 2

在人类的历史长河中，每个人都可能要与其他人握手。如果某人在他的一生中进行握手的次数为奇数，则称他为A类人，否则称为B类人。从古至今A类人的个数是偶数。如何用图的相关理论解释？

无向图的边数等于各顶点度数之和的一半。

Task 3

若$G$是简单无向图，$A$为$G$的邻接矩阵，$M$为$G$的关联矩阵，$D$是对角线上第i个元素为顶点的度的对角矩阵，则它们的关系是：$A+D=M{M}^T$。

证明：（ChatGPT）

要证明对于简单无向图 $G$，其邻接矩阵 $A$、关联矩阵 $M$ 和度矩阵 $D$ 满足关系 $A+D=M{M}^T$，我们可以按以下步骤进行。

步骤 1：定义和性质

1. 邻接矩阵 $A$:

• 如果 $G$ 有 $n$ 个顶点和 $m$ 条边，$A$ 是一个 $n\times n$ 的矩阵。
• $A_{ij}$ 表示顶点 $i$ 和顶点 $j$ 之间是否存在边。
• $A$ 是对称矩阵，且对角线上全为0。

2. 关联矩阵 $M$:

• $M$ 是一个 $n\times m$ 的矩阵，表示顶点和边的关系。
• 如果边 $e_k$ 连接顶点 $v_i$ 和 $v_j$，则 $M_{ik}$ 和 $M_{jk}$ 都为1（假设无向边）。

3. 度矩阵 $D$:

• $D$ 是一个 $n\times n$ 的对角矩阵。
• $D_{ii}$ 表示顶点 $v_i$ 的度数，即与顶点 $v_i$ 相连的边的数量。

步骤 2：计算 $M{M}^T$

• $M$ 的每一列代表一条边，两行之间的相应位置表示这两个顶点是否共享一条边。
• $M{M}^T$ 的结果将是一个 $n\times n$ 的矩阵，其中每个元素 $(i,j)$ 表示顶点 $v_i$ 和顶点 $v_j$ 共享的边的数目。

更具体地说：

• $(M{M}^T{)}_{ij}=\sum _{k=1}^m{M}_{ik}{M}_{jk}$
• 对于 $i\ne j$，$(M{M}^T{)}_{ij}$ 表示顶点 $v_i$ 和顶点 $v_j$ 之间是否有边，即 $A_{ij}$。
• 对于 $i=j$，$(M{M}^T{)}_{ii}$ 表示顶点 $v_i$ 的度数，即 $D_{ii}$。

步骤 3：证明关系 $A+D=M{M}^T$

对于 $i\ne j$：

$$(M{M}^T{)}_{ij}=\sum _{k=1}^m{M}_{ik}{M}_{jk}=A_{ij}$$

这是因为 $A_{ij}$ 表示顶点 $v_i$ 和顶点 $v_j$ 之间是否有边。

对于 $i=j$：

$$(M{M}^T{)}_{ii}=\sum _{k=1}^m{M}_{ik}{M}_{ik}=\text{deg}(v_i)$$

这是因为 $\text{deg}(v_i)$ 是顶点 $v_i$ 的度数，即与顶点 $v_i$ 相连的边的数量，等于度矩阵 $D$ 中对应的对角元素。

因此，我们得到：

$$A_{ij}+D_{ii}=(M{M}^T{)}_{ij}$$

其中 $A_{ii}=0$，$D_{ij}=0$ 对于 $i\ne j$。于是：

$$A+D=M{M}^T$$

这完成了证明。