邓俊辉《数据结构》-复杂度/递归学习笔记

ゝ一世哀愁。 2023-10-01 08:23 21阅读 0赞

**目录**

2021.12.4 星期六

冒泡排序 bubblesort

swap()函数

迭代与递归

2021.12.6 星期一

1<<2

分而治之

fib()

动态规划

最长公共子序列 LCS

--------------------

## 2021.12.4 星期六 ##

复杂度分析：循环分析

### **冒泡排序 bubblesort**  ###

简介：排序过程中，相邻元素不断交换，一些元素被慢慢换到最后，看起来就像是元素在冒泡一样。

**算法原理：**以递增为例，从头开始比较相邻的两个元素，如果第i比第i+1大，则掉换二者位置，再进行下一个相邻的比较，这就是一次循环。下一次循环再从头开始，每次都循环直到没有发生元素交换，则说明第i个元素都比第i+1个元素小，则冒泡排序完成。

时间复杂度：内循环首先要扫描n-1对相邻元素，**最坏的结果**也是交换n-1次，而元素的比较&元素的交换都是基本操作，因此需要2(n-1)次操作。外循环**最多**循环n-1次。因此整体的时间复杂度：T(n)=O(2(n-1)²)=O(n²)

C++代码实现：

#### swap()函数 ####

交换了swap(A,B)中A,B的值

void bubblesortA(int A[],int n){
    bool sorted=false; //初始假定尚未排序
    while(!sorted){
    sorted=true;
    for(i=1;i<n;i++){
    if(A[i-1]>A[i]){
    swap(A[i-1],A[i]);
    sorted=false;//证明还没有整体排序完成，清楚排序标志
    }
    }
    n--;//每次排序必然保证最后一个是全场最大的，因此减少一次比较
    }
    }

void bubblesortA(int A[],int n){
    for(bool sorted=false;sorted=!sorted;n--){
    for(i=1;i<n;i++){
    if(A[i-1]>A[i]){
    swap(A[i-1],A[i]);
    sorted=false;//证明还没有整体排序完成，清楚排序标志
    }
    }
    n--;//每次排序必然保证最后一个是全场最大的，因此减少一次比较
    }
    }

### 迭代与递归 ###

计算任意n个整数之和

迭代：

int SumI(int A[],int n){
    int sum=0;
    for(i=0;i<n;i++){
    sum+=A[i];
    }
    return sum;

**递归：减而治之**

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

## 2021.12.6 星期一 ##

### 1<<2 ###

<<的意思，是将1的二进制编码向左移动2位，由 00000001 变成 00000100

值由1变成4

同理，>>向左移动

### 分而治之 ###

//举例子：
    sum(int A[], int lo, int hi){ //求A[]数组中从lo到hi中的和
    if(lo==hi) return A[lo]; 
    int mi = (lo+hi)>>1; //一分为二
    return sum(A,lo,mi)+sum(A,mi,hi);
    }

分而治之是将计算分成：1次规模为n，两次规模为n/2, 四次规模为n/4... 1+2+4+...+n

减而治之是越来越小：1+2+...+n

### fib() ###

斐波那契数列，又叫黄金分割数列/兔子数列，F(0)=0,F(1)=1... **核心思想：**F(n)=F(n-1)+F(n-2)

**递归版本：**

int fib(){
    return (n<2)? n: fib(n-1)+fib(n-2);
    }

递归版本的会重复利用递归实例，时间和空间都用得很多。如果用迭代的方法呢？

### 动态规划 ###

颠倒计算方法，从递归基出发，由自顶而下递归，变成自底而上迭代，**迭代版本：**

fib(){
    int f=0,b=1;
    while(n-->0){
    b=b+f;
    f=b-f;
    }
    return b;
    }

### 最长公共子序列 LCS ###

可能有多个公共子序列，因此只需找出其中一个或者**最长的长度**