题目来源:挑战程序设计竞赛
题目描述:
给定n个数字,选择四次,可以选择已经选择过的数字,问是否可以选出和为m的四个数。
首先,最基本的做法:
枚举四层,每一层枚举出一个数,求出所有四个数字不同的排列。时间复杂度为O(N^4)。
for (int i1=1;i1<=n;i++)
for (int i2=i1;i2<=n;i2++)
for (int i3=i2;i3<=n;i3++)
for (int i4=i3;i4<=n;i4++)
让我们来一步步优化吧。
基本做法的本质是,枚举前三个数字,然后找出来一个可以凑成正确解的数字,找到了,则有答案,否则,继续枚举前三个数。
也就是说,最后一层枚举,本质是一个查找的过程,我们使用了O(N)的查找方式。
显然对于查找,有很多可以优化的方法,散列表,二分法,我们这里使用二分法,先把数排序,再用二分查找。时间复杂度变为O(N^3*logN)
再看,四个数字,枚举三个数的组合再找,可不可先求出两两数字之和,然后第一层枚举这些和,第二层从这些和中找出一个符合的解?
先枚举出和,N^2,再查找,logN^2
时间复杂度为N^2*logN
个人感觉,最后的优化多少本身都是带着些”二分问题“的思想在里面的。
一道简单题目的优化过程——抽签问题,布布扣,bubuko.com
原文:http://www.cnblogs.com/dandi/p/3885446.html