《算法笔记》总结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;
}

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