分治法解矩阵乘积

题目假设有A,B两个矩阵,且其均为n*n维矩阵,n为2的幂(n>=2)。求A与B的乘积。分治法解矩阵乘积通过上图我们可以看到书中的利用分治法解决的伪代码。解决思路一暴力解法时间复杂度O(n^3程序范例void solve_matrix_multiply_n3(int a[][MATRIX_LENGTH], int b[][MATRIX_LENGTH], int c[][MATRIX_LENGTH]for (int i = 0; i < MATRIX_LENGTH; i++) for (int j = 0; j < MATRIX_LENGTH; j++) for (int k = 0; k < MATRIX_LENGTH; k++) c[i][j] += a[i][k] * b[j][k];解决思路二利用分治法解决矩阵乘积程序范例void solve_matrix_mul... Read More

分治法策略解决最大子数组问题

问题描述Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4]the contiguous subarray [4,−1,2,1] has the largest sum = 6.问题来自于Leetcode:Maximum Subarra解决方式利用分治策略来解决最大子数组问题时间复杂度O(nlgn程序范例[code lang="cpp"#include <iostr#include <cstdusing namespace std;int find_max_crossing_subarray(int* a, int... Read More

分治法的经典运用归并排序(Merge Sort)

简介归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。分类排序算法数据结构数组最差时间复杂度最优时间复杂度平均时间复杂度最差空间复杂度归并操作归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。迭代法申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列设定两个指针,最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针到达序列尾将另一序列剩下的所有元素直接复制到合并序列尾递归法原理如下(假设序列共有n个元素)... Read More