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

一.打表

        一种经典的空间换时间方式:即将所有可能用到的结果实现计算出来,这样后面用到的时候直接可以查表获得。具体来说有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;
}

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

07-24 18:55