分治策略-白红宇

分治策略

阅读量：6283 次

发布时间：2019-06-22

本文共 3361 字，大约阅读时间需要 11 分钟。

1、二分查找

(1)、二分查找递归实现

#include
     
      #define NOT_FOUND    -1;int binSearch(int *a, int head, int tail, int key);int binSearch(int *a, int head, int tail, int key){    int middle;    if(head <= tail){        middle = (head + tail)/2;        if(key == a[middle]){            return middle;        }        if(key < a[middle]){            return binSearch(a, head, middle-1, key);        }        if(key > a[middle]){            return binSearch(a, middle+1, tail, key);        }    }    return NOT_FOUND;}void main(void){    int a[] = {2, 3, 4, 6, 8, 10};    int count = sizeof(a)/sizeof(int);    int index;    int number;    printf("请输入要查找的数字: ");    scanf("%d", &number);    index = binSearch(a, 0, count-1, number);    printf("%d\n", index);}

(2)、结果截图

(3)、二分查找非递归实现

#include
     
      #define NOT_FOUND    -1int binSearch(int *a, int count, int key);int binSearch(int *a, int count, int key){    int head = 0;    int tail = count-1;    int middle = (head+tail)/2;    while(head <= tail){   //有可能head和tail到达了同一个数字;        if(key < a[middle]){            tail = middle-1;        }else if(key > a[middle]){            head = middle+1;        }else{            return middle;        }        middle = (head+tail)/2;    }    return NOT_FOUND;}void main(void){    int a[] = {1, 3, 6, 8, 9, 10};    int count = sizeof(a)/sizeof(int);    int number;    int index;    printf("请输入要查找的数字：");    scanf("%d", &number);    index = binSearch(a, count, number);    printf("%d\n", index);}

(4)、结果截图

(5)、算法分析

时间复杂度为：O(logn);

二分查找使用场合：i、连续的物理内存空间(数组)；ii、已经排好序了(升序/降序)；

2、乘方问题，给你一个数X，然后在给你一个正整数n，计算x的n次方？

时间复杂度为：O(n);

怎么用分治法，在非线性时间内解决这个问题？

分解为2个子问题是完全一样的，所以时间复杂度为：O(logn);

3、斐波那契数列：输入n,求第n项？

(1)、递归代码实现

#include
     
      int fibonacci(int n);int fibonacci(int n){    if(n <= 0){        return 0;    }    if(n == 1){        return 1;    }    return fibonacci(n-1)+fibonacci(n-2);}void main(void){    int number;    int value;    printf("请输入斐波那契数：");    scanf("%d", &number);    value = fibonacci(number);    printf("%d\n", value);}

算法分析：

这就是一个递归树，处理相同的子问题，用的分治策略，在递归树上好多都是重复计算的；

时间复杂度(指数级)：

(2)、非递归算法

#include
     
      int fibonacci(int n);int fibonacci(int n){    int firstNumber = 0;    int secondNumber = 1;    int finNumber;    int i = 2;    if(n == 1){        return firstNumber;     }    if(n == 2){        return secondNumber;    }    for(i = 3; i <= n; i++){        finNumber = firstNumber + secondNumber;        firstNumber = secondNumber;        secondNumber = finNumber;    }    return finNumber;}void main(void){    int number;    int value;    printf("请输入第几个斐波那契数：");    scanf("%d", &number);    value = fibonacci(number);    printf("%d\n", value);}

算法分析：

时间复杂度：O(n);

(3)、公式法

算法分析：

这种方法在实际上不能实现，浮点数包含在内，取整将得不到正确答案；

(4)、平方递归算法

矩阵相乘法：

证明：

算法分析：

时间复杂度为：O(logn);

4、NxN矩阵乘法，具体描述为(矩阵乘法的顺序是不可以交换的)：

(1)、用上面的这个公式实现算法，嵌套三层for循环；