《算法笔记》总结No.9——高效配招

一.打表

        一种经典的空间换时间方式：即将所有可能用到的结果实现计算出来，这样后面用到的时候直接可以查表获得。具体来说有3种方式：

1.计算所有结果

        这个是最常用到的用法，例如在一个需要查询大量Fibonacci数F(n)的问题中，显然每次从头开始计算是非常耗时的，对Q次查询会产生O（nQ）的时间复杂度;而如果进行预处理，即把所有Fibonacci数预先计算并存在数组中，那么每次查询就只需要O(1)的时间复杂度，对Q次查询就只需要O（n+Q）的时间复杂度(其中O(n)是预处理的时间)。

2.程序B来保存

        这种用法般是当程序的一部分过程消耗的时间过多，或是没有想到好的算法，因此在另一个程序中使用暴力算法求出结果，这样就能直接在原程序中使用这些结果。例如对皇后问题来说，如果使用的算法不够好，就容易超时，而可以在本地用程序计算出对所有来说2皇后问题的方案数，然后把算出的结果直接写在数组中，就可以根据题目输入的来直接输出结果。

3.暴力缩小

        对于不太会做的题目，先用程序暴力计算小范围的数据结果，然后找规律或许可以发现一些蛛丝马迹，这种方法在数据非常大的时候容易用的到~

二.递推

• 递归：从上到下 从未知到已知解决问题
• 递推：从下到上 从已知到未知解决问题

DP主要通过递推实现。

三.随机选择算法 

        原理：在数组中随机选取一个数作为分隔值a，将小于a的数放到a的左边，大于a的数放到a的右边，之后再递归排列右数组和左数组。

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int first,last;
void swap(vector<int>& nums, int first, int i) {
int a = nums[first];
nums[first] = nums[i];
nums[i] = a;
}
void partion(vector<int>& nums, int l, int r, int x) {
first = l;
last = r;
int i = l;
while (i <= last) {
if (nums[i] == x)
i++;         
else if (nums[i] < x) {
swap(nums,first, i);
first++;
i++;
}
else {
swap(nums, last, i);
last--;
}          

}
 
 }
void quicksort(vector<int>& nums,int l,int r) {
if (l >= r) return;
int x = nums[l + rand() % (r - l + 1)];
partion(nums, l, r, x);
int left = first - 1;
int right = last + 1;
quicksort(nums, l, left);
quicksort(nums, right, r);
 }
 
int main() {
vector<int> nums;
int num;
cout<<"请输入总数：";
cin>>num;
for(int i=1;i<=num;i++)
{
int temp=0;
cin>>temp;
nums.push_back(temp);
} 

quicksort(nums, 0, nums.size() - 1);
for (int i = 0; i < nums.size(); i++)
cout << nums[i] << " ";
return  0;
}

---

为了尽可能保证质量，近期更新不快见谅~

原文地址：https://blog.csdn.net/jsl123x/article/details/140504226

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！