算法设计与分析复习02：分而治之算法

曾经终败给现在 2024-03-30 13:33 55阅读 0赞

> 作者：非妃是公主  
> 专栏：《算法》  
> **个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩**
> 
> ![在这里插入图片描述][7cea80270e124c7faeb5f6b5fd8ac41a.jpeg]
> 
> ### 专栏系列文章 ###
> 
> [算法设计与分析复习01：主方法求递归算法时间复杂度][01]
> 
> [算法设计与分析复习02：分而治之算法][02]
> 
> [算法设计与分析复习03：动态规划算法][03]  
> [算法设计与分析复习04：贪心算法][04]
> 
> [算法设计与分析复习05：回溯及分支限界][05]
> 
> [算法设计与分析复习06：随机化算法][06]
> 
> [算法设计与分析复习07：样题][07]
> 
> #### 文章目录 ####
> 
>  *   *  专栏系列文章
>      *  复习重点
>      *  分而治之算法
>      *   *  全排列递归算法
>          *  矩阵乘法的Strassen算法
>          *  棋盘覆盖
>          *  线性时间选择

### 复习重点 ###

![在这里插入图片描述][16ee73d314d24fd7a218b4b65604a9f6.png]

### 分而治之算法 ###

#### 全排列递归算法 ####

![在这里插入图片描述][e6b9c6f473124f6599a213378e40204c.png]![在这里插入图片描述][9326958b2ccc4fd8b0796693a08579cd.png]

#include<vector>
    #include<iostream>
    using namespace std;
    class Solution {
        
        vector<int> vis;
        void backtrace(vector<vector<int>>&res,vector<int>&nums,int first,int len, vector<int>& perm) {
        
            if (first == len) {
        
                res.push_back(perm);
            }
            else {
        
                for (int i = 0; i < len; i++) {
        
                    if (vis[i])continue;
                    perm.emplace_back(nums[i]);
                    vis[i] = 1;
                    backtrace(res, nums, first + 1, len, perm);
                    vis[i] = 0;
                    perm.pop_back();
                }
            }
        }
    public:
        vector<vector<int>> permute(vector<int>& nums) {
        
            vector<vector<int>>res;
            vector<int> perm;
            vis.resize(nums.size());
            backtrace(res, nums, 0, nums.size(), perm);
            return res;
        }
    };
    int main() {
        
        Solution solution;
        vector<int> v = {
         1,2,3 };
        vector<vector<int>> res = solution.permute(v);
        for (auto it = res.begin(); it != res.end(); it++) {
        
            for (auto it1 = it->begin(); it1 != it->end(); it1++) {
        
                cout << *it1 << " ";
            }
            cout << endl;
        }
        return 0;
    }

#### 矩阵乘法的Strassen算法 ####

![在这里插入图片描述][08fd929683694fbba13bcb02d1608981.png]  
![在这里插入图片描述][0a1ef1b0b8054bde833f0f12a1ba4e7f.png]  
![在这里插入图片描述][2ba0822702514a46a7aa6ef5e49d2674.png]  
![在这里插入图片描述][0ef8c2b7bdb94283b0f7b09be156e91d.png]  
\[Strassen算法步骤\]([详解矩阵乘法中的Strassen算法 - 知乎 (zhihu.com)][Strassen_ - _ _zhihu.com])

算法分析：  
 T ( n ) = \{ O ( 1 ) n=1 7 T ( n 2 ) + O ( n 2 ) n>1 T(n)=\\left\\\{ \\begin\{matrix\} O(1)& \\text\{n=1\} \\\\ 7T(\\frac\{n\}\{2\})+O(n^2)& \\text\{n>1\} \\end\{matrix\} \\right. T(n)=\{ O(1)7T(2n)\+O(n2)n=1n>1  
主方法求得算法复杂度为：  
 n l o g 2 7 n^\{log\_\{2\}\{7\}\} nlog27

#### 棋盘覆盖 ####

棋盘覆盖问题看下面这张图，由于要求期盼规模为  
 2 k × 2 k 2^k\\times2^k 2k×2k  
有一定的局限性，但是是理解递归与分治的好问题，只看下面这张图：  
![在这里插入图片描述][df90ada2923b4a4d8a4bf2eed4515888.png]  
每一个块对称选择。

#### 线性时间选择 ####

主要思想：利用快排，进行部分排序，不断缩小范围。  
核心代码：  
![在这里插入图片描述][a7a0e8f572ca4cb5a6d07d3f593c0f96.png]  
全部代码：

#include<vector>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    
    using namespace std;
    
    class Solution {
        
        struct num_mid {
        
            int pos;
            int num;
            bool operator<(const num_mid nm) {
        
                return this->num < nm.num;
            }
            num_mid(int p, int n) :pos(p), num(n) {
        }
        };
        int Partition(vector<int>& Vector, const int low, const int high) {
        
            //数据表类的共有函数
            int pivotpos;
            int pivot; //基准元素
            if (high - low > 5) {
        
                vector<num_mid>tmp;
                for (int i = low; i <= high - 4; i += 5) {
        
                    sort(Vector.begin() + i, Vector.begin() + i + 4);
                    tmp.push_back(num_mid(i + 2, Vector[i + 2]));
                }
                sort(tmp.begin(), tmp.end());
                pivotpos = low;
                pivot = Vector[tmp[tmp.size() / 2].pos];
                swap(Vector[low], Vector[tmp[tmp.size() / 2].pos]);
            }
            else {
        
                sort(Vector.begin() + low, Vector.begin() + high);
                pivotpos = low;
                pivot = Vector[(low + high) / 2]; //基准元素
                swap(Vector[low], Vector[(low + high) / 2]);
            }
            for (int i = low + 1; i <= high; i++)
                //检测整个序列, 进行划分
                if (Vector[i] < pivot) {
        
                    pivotpos++;
                    if (pivotpos != i)
                        swap(Vector[pivotpos], Vector[i]);
                } //小于基准的交换到左侧去
            Vector[low] = Vector[pivotpos];
            Vector[pivotpos] = pivot;
            //将基准元素就位
            return pivotpos; //返回基准元素位置
        }
    
        int QuickSort(vector<int>& L,
            const int left, const int right, int k) {
        
            //对元素Vector[left], ..., Vector[right]进行排序, 
            //pivot=L.Vector[left]是基准元素, 排序结束后它的
            //位置在pivotPos, 把参加排序的序列分成两部分,
            //左边元素的排序码都小于或等于它, 右边都大于它
            if (left < right) {
         //元素序列长度大于1时
                int res;
                int pivotpos = Partition(L, left, right); //划分
                if (pivotpos > k)
                    res = QuickSort(L, left, pivotpos - 1, k);
                else if (pivotpos < k)
                    res = QuickSort(L, pivotpos + 1, right, k);
                else
                    return L[pivotpos];
                return res;
            }
            else
                return L[left];
        }
    public:
        int findKthLargest(vector<int>& nums, int k) {
        
            int res = QuickSort(nums, 0, nums.size() - 1, nums.size() - k);
            return res;
        }
    };
    
    int main() {
        
        vector<int> v = {
         3,2,3,1,2,4,5,5,6 };
        int res = QuickSort(v, 0, v.size() - 1, v.size() - 4);
        cout << res;    
    }

时间复杂度分析：假设，基本实现二分，线性选择支点的时间复杂度为 O ( n ) O(n) O(n)，递归的时间复杂度如下：  
 T ( n ) = T ( n 2 ) + O ( n ) T(n)=T(\\frac\{n\}\{2\})+O(n) T(n)=T(2n)\+O(n)  
依据主定理，时间复杂度为 O ( n ) O(n) O(n)。

[7cea80270e124c7faeb5f6b5fd8ac41a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b76cc67bb2894465bc77f8559b0a3f1d.jpeg
[01]: https://blog.csdn.net/myf_666/article/details/128509102
[02]: https://blog.csdn.net/myf_666/article/details/128509126
[03]: https://blog.csdn.net/myf_666/article/details/128509143
[04]: https://blog.csdn.net/myf_666/article/details/128509159
[05]: https://blog.csdn.net/myf_666/article/details/128509168
[06]: https://blog.csdn.net/myf_666/article/details/128509174
[07]: https://blog.csdn.net/myf_666/article/details/128509183
[16ee73d314d24fd7a218b4b65604a9f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ae35e7673de2443391bc6d10c7945866.png
[e6b9c6f473124f6599a213378e40204c.png]: https://img-blog.csdnimg.cn/e6b9c6f473124f6599a213378e40204c.png
[9326958b2ccc4fd8b0796693a08579cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fe25f23610f3452285190e55aa32a4e3.png
[08fd929683694fbba13bcb02d1608981.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/32bc836d75e447e7b2b5a4f7f6cb91e2.png
[0a1ef1b0b8054bde833f0f12a1ba4e7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e37677b47d684bacba09b3318f32f60e.png
[2ba0822702514a46a7aa6ef5e49d2674.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b4b6563b61904dc4b9d9e3537d86a73b.png
[0ef8c2b7bdb94283b0f7b09be156e91d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e994ad8dca8f41a9acac5854c03eff25.png
[Strassen_ - _ _zhihu.com]: https://zhuanlan.zhihu.com/p/78657463
[df90ada2923b4a4d8a4bf2eed4515888.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7d7dca36b6cf47d4922c04b0c2315e33.png
[a7a0e8f572ca4cb5a6d07d3f593c0f96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d58f7e1635914b0298b6b7125bb7b4f5.png