邓俊辉<<数据结构>>-公开课-01-E

发表于

迭代与递归

分而治之：分解成子问题，递归式的求解。

空间复杂度：指不包含算法的输入本身所占的空间之外，所需要的另加的用于计算所必须的空间总量。

减而治之

 合                合并
---->    问题   --------
^      /      \        ^
| 缩减/        \ 平凡   |
|	   /          \       |
 -> 子问题     子问题 <---
 !     !         !    !
 -------         ------
   治              治

-—例子1—–
求n个总数之和

int sum(int A[], int n) {
  // A为整数数组, n为问题规模, 返回数组中整数的总和
  return
      (n < 1) ?
      0 : sum(A, n-1) + A[n-1];
}

分析:

  • 该问题分解为一个缩减问题sum(A, n-1) 和 一个平凡问题A[n-1]
  • 最后规模小到一定程度时， 缩减问题变为 平凡问题
  • 将两个问题合并得到结果

复杂度如何？

递归跟踪(recursion trace)分析 (用于简单的递归)

  • 检查每个递归实例
  • 累积所需要时间（调用语句本身抹去，计入递归实例）
  • 其总和是算法执行时间
    || ||
    vv vv
    线性递归：得出上述递归是线性递归，复杂度渐进O(n)

递推方程分析 (用于复杂的递归)
上述例子中:
T(n) = T(n-1) + O(1) // recurrence
T(0) = O(1) // base

T(n) - n = T(n-1) - (n-1) = T(n-2) - (n-2) ...
         = T(2) - 2
		 = T(1) - 1
		 = T(0) - 0 = O(1)

T(n) = O(1) + n = O(n)

-——例子2—————–
任给数组A[0,n), 将其前后颠倒 // 更一般的子区间[lo, hi]
统一接口 : void reverse(int * A, int lo, int hi);

递归版

规模缩小两个单位。

void reverse(int* A, int lo, int hi) {
  // 输入指向数组A的指针, A中要转置的左区间lo， A中要转置的右区间lo
  // 无返回值，改变指针A所指向的数组, 使其倒序
  if (lo < hi) {
    swap(&(A[lo]), &(A[hi]));
    if (((hi-lo) == 1) || ((hi - lo) == 0)) return;
    reverse(A, lo + 1, hi - 1);
  }
}

分析时间复杂度：

递归跟踪(recursion trace)

int main();
reverse(A[n], lo, hi);
reverse(A[n-2], lo+1, hi-1);
reverse(A[n-4], lo+2, hi-2);
...

reverse(A[1], lo+(n-1)/2, hi+(n-1)/2);
or
reverse(A[0], lo + n/2, hi+ n/2);
      (n-1)/2 , n是奇数
     /                   
O(1)*                    = O(n)
     \n / 2,    n是偶数

递推方程

T(n) = T(n) + O(1);
T(n) - n = T(n-1) - (n-1)
T(n) - n = T(2) - 2
         = T(0) - 0
T(n) = T(0) + n = O(n)

<span style=”color”:blue”>感觉不怎么正确??

课后推敲:

迭代原始版本

void reverse_iterate_original(int* A, int lo, int hi) {
  // 迭代原始版本
next:
  if (lo < hi)
  {swap(&A[lo], &A[hi]); lo++; hi--; goto next;}
}

使用next作为分支标记,goto跳转，真的能让代码运行，从来没用过

迭代精简版

void reverse_iterate(int* A, int lo, int hi) {
  // 迭代版本
  while (lo < hi) swap(&A[lo++], &A[hi--]);
}

分而治之(divide-and-conquer)

分解为多个或两个子问题，得到解后归并。
-—–二分递归———-

int mid_sum(int A[], int lo, int hi) {
  // 数组求和 :二分递归
  if (lo == hi) return A[lo];
  int mid = (lo + hi) >> 1;
  return mid_sum(A, lo, mid) + mid_sum(A, mid + 1, hi);
}

注意 mid + 1

// 分析:
// 被分解成两个相似问题，mid_sum(n/2)
// 规模每次缩减一半，最后到达递归基
// 将多个问题结果合并

分析复杂度:

递归跟踪(几何归纳)

以2为倍数的几何级数，总和与末项同阶。

递推方程(代数运算)

两个问题都是n/2
累加O(1)时间
递归基O(1)时间返回

递推关系
T(n) = 2* T(n/2) + O(1)
T(1) = O(1)

..
T(n) = O(n)

Max2: 迭代1

从数组区间A[lo, hi)中找出最大的两个整数A[x1]和A[x2] // A[x1] > A[x2]
比较次数要尽可能的少

int max2_three_iters(int A[], int lo, int hi) {   // 1 < n = hi - lo
  int max1 = 0, max2 = 0;
  int x1, x2;
  if (hi < lo) return -1;
  for (int i = lo; i <= hi; i++)
    if (max1 < A[i]) {max1 = A[i]; x1 = i;}       // hi-lo-1 = n-1

  if (x1 != lo) {
    for (int i_lo  = lo; i_lo < x1; i_lo++)
      if (max2 < A[i_lo]) {max2 = A[i_lo]; x2 = i_lo;} // x1-lo-1
  }
  if (x1 != hi) {
    for (int i_hi = x1+1; i_hi <= hi; i_hi++)
      if (max2 < A[i_hi]) {max2 = A[i_hi]; x2 = i_hi;} // hi-x1-1
  }
  int max_array[2] = {max1, max2};
  std::cout << " A[x1] = " << A[x1] << '\n'
            << " A[x2] = " << A[x2] << std::endl;
}

总共比较n-1+n-2 =2n-3 

int max2(int A[], int lo, int hi) {
  // 遍历一次，改变指针
  int* x1 = &lo;
  int lo_next = lo + 1;
  int* x2 = &lo_next;
  if (A[*x1] < A[*x2]) {x1 = &lo_next; x2 = &lo;}
  for (int i = lo + 2; i <= hi; i++) {
    if (A[*x2] < A[i]) {      // 索引i的对象比较小的值大
      if (A[*x1] < A[i]) {    // 索引i的对象甚至超过了较大值
        x2 = &(*x1); x1 = &i;
        break;
      }
      *x2 = i;                // x1指针指向的元素赋值成i
    }
  }
  std::cout << " A[*x1] "  << A[*x1] << '\n'
            << " A[*x2] "  << A[*x2] << std::endl;
}

最好情况: 1 + (n-2)1 = n-1
最坏情况: 1+ (n-2) 2 = 2n-3

即使在最坏情况，也更高效的改进算法

  • 分而治之
  • 实现退化情况
void max2(int A[], int lo, int hi, int & x1, int & x2) {     // [lo, hi)
  if (lo + 2 == hi) {
    if (A[lo] < A[lo+1]) {
      x1 = A[lo+1]; x2 = A[lo];
    } else {
      x2 = A[lo+1]; x1 = A[lo];
    }
    return;
  }                         // T(2) = 1
  if (lo + 3 == hi) {       // lo, lo+1, lo+2, lo+3; 19, 2, 3, -1;
    x1 = lo, x2 = lo+1;
    if (A[x1] < A[x2]) {x1 = lo+1; x2 = lo;}
    for (int i = lo+2; i < hi+1; i++) {
      if (A[i] > A[x2]) {
        if (A[i] > A[x1]) {
          int tmp = x1;
          x1 = i; x2 = tmp;
          break;
        }
        x2 = i;
      }
    }
    return;
  }                         // T(3) <= 3
  int mid = (lo + hi) >> 1;
  int x1L, x2L; max2(A, lo, mid, x1L, x2L);
  int x1R, x2R; max2(A, mid+1, hi, x1R, x2R);
  if (A[x1L] > A[x1R]) {
    x1 = x1L; x2 = (x2L < x1R) ? x1R:x2L;
  } else {
    x1 = x1R; x2 = (x2R < x1L) ? x1L:x2R;
  }
} // 1 + 1 = 2

最坏情况: T(n) = 2 * T(n/2) + 2 <= 5n/3 -2

递推方程推导过程: ?

最好情况复杂度: ?

总结

两种重要算法策略：减而治之，分而治之

两种分析方法：递归跟踪和递推方程