算法设计

[code=BatchFile]输入、输出范例输入：{ 1, 4, 2, 3 }
输出：1+3=4输入：{ 2, 3, 1, 4, 5 }
输出：2+3=5输入：{ 5, 8, 3, 1, 2, 4, 4 }
输出：4+4=8输入：{ 4, 4, 5, 0, 1, 2, 3, 8, 9, 9, 100 }
输出：0+9=9[/code]

你这样做复杂度是n，不是O(nlog(n)) or O(n^2)关注。想看到正确的算法！

有点难度，我觉得应该是 0(n^2)， o(nlog(n))难度有点大，除非本身是排序的

思路：首先按大到小排序，排序后又三次循环：
第一次循环取最大值max，循环计数i
第二次循环，取一个加数b[j]，并且循环计数j!=i，算出max-b[j]
第三次循环，取另一个加数，判断b[k] == max-b[j]，并且循环计数k != i && k != j;代码：package com.test;public class ArrayNum {

public static int[] order(int[] a){
for (int i = 0; i<a.length; i++){
for (int j = i; j<a.length; j++){
int temp;
if (a[i] < a[j]){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
return a;
}

public static void main(String[] args){
// int[] a = { 4, 4, 5, 0, 1, 2, 3, 8, 9, 9, 100 };
int[] a = { 5, 8, 3, 1, 2, 4, 4 };

int[] b = ArrayNum.order(a);

for (int i = 0; i<b.length; i++){
int max = b[i];
for (int j = 0; j<b.length; j++){
if (j == i){
continue;
}
int temp = max - b[j];
for (int k = 0; k<b.length; k++){
if (temp == b[k] && j != k && k != i){
System.out.println(b[j] + "+" + b[k] + "=" + max);
return;
}
}
}
}
System.out.println("没有该数字!");
}}

引用 6 楼 renmms 的回复:
引用 5 楼 llliiiuuu 的回复:
一、获取最大的数
二、循环数组，最大的数减去当前的数得到结果，然后查找数组中有没有这个结果，有就打印
你这样做复杂度是n，不是O(nlog(n)) or O(n^2) 关注。想看到正确的算法！复杂度是怎么算的,我觉得这个算法不止n

我认为排序还是需要的
如：采用快速排序呢，需要O(nlgn)

(引用一个想法)O(n^2)的
[code=BatchFile]1）先排序,o(nlogn);
2) 对单个的A[i]，判断是否存在A[i]=A[x]+A[y],0 <=x <y <i <N, o(n)
  x=0;y=N-1;
  while(y>x)
  {
  if (x==i) x++;
  else if (y==i) y--;
  else if (a[x]+a[y]==a[i]) return 1；
  else if (a[x]+a[y]>a[i]) y--;
  else if (a[x]+a[y] <a[i]) x--;
  }
  return 0;[/code] 这样对所有的A[i]，0 <=i <N，进行判断的复杂度就是o(n^2)的；

对数组里的数两两相加就要O(n^2)了，除非谁想出来的算法不用两两相加，要不然就不会低于O(n^2)。

我没学过算法，把这个当数学题来做，失败了..
可以把数组中的数值看做是一个个函数值f(x),数组下标看做x坐标
这样在二维数组中就形成了一系列散点.
于是题目可以等价于对函数y = f(x),求出x1,x2,x3∈【0，n - 1】，使得f(x3) = f(x1) + f(x2),
再找出最大的f(x);
在草图上，可以看出这个表达式f(x3) = f(x1) + f(x2)隐含这一个面积属性
即：由四点（x1, f(x1)），（x1, 0）, (x2, f(x2)), (x2, 0)形成的梯形面积 = 由三点(x3, f(x3)), (x1, 0) ,(x2, 0)形成的三角形面积
于是可以通过不同的求面积方法建立等式..
一种的普通的底乘以高除以2
一种是用2次拉格朗日插值函数得到过三点(x1, f(x1)),(x2, f(x2), (x3, f(x3)))的精确函数,再用牛顿积分对区间[x1, x2]求积分
但是这样一来问题就搞复杂了...失败了

应该也可以采用矩阵来做，但我还没有想到一个O(nlgn)的方法

算法分析：
关键点有两个，一个是构成所有的任意两数之和的集合；另一个是从集合中找到与原数组中相同的项。
/**
*
*/
package houlei.test;import java.util.Arrays;/**
*
*
* 该类创建于 2008-11-25 上午11:22:47
* @version 1.0.0
* @author 侯磊
*/
public class TestMain { public static void main(String[] args) {
int[] a0= new int[]{ 1, 4, 2, 3 };
//输出：1+3=4
int[] a1= new int[]{ 2, 3, 1, 4, 5 };
//输出：2+3=5
int[] a2= new int[]{ 5, 8, 3, 1, 2, 4, 4 };
//输出：4+4=8
int[] a3= new int[]{ 4, 4, 5, 0, 1, 2, 3, 8, 9, 9, 100 };
//输出：0+9=9
test(a0);
test(a1);
test(a2);
test(a3);
} private static void test(int[] a) {
long start = System.nanoTime();
find(a);
long end = System.nanoTime();
System.out.println("查找结束，共花费了 "+(end-start)+" 纳秒。");
}

/**
* 算法核心内容
*/
private static void find(int [] a){
if(a==null)return;
if(a.length<2)return;
Arrays.sort(a);//将输入数组排序。
//构建a中任意两数之和的集合(上三角形矩阵）
int temp [][] = new int[a.length][a.length];
for(int i=0;i<a.length;i++){
for(int j=i;j<a.length;j++){
temp[i][j]=a[i]+a[j];
}
}
//遍历temp的有效元素，找出与a中元素相同的项，并显示结果。
int max = a.length-1;//创建a的最大值变量，用于优化查找性能。
int index = 0;//创建比较数组的附加位置，用于提升查找性能。
for(int j=1;j<a.length;j++){
for(;index<a.length&&temp[0][j]>a[index];index++);//向后移动查找的初始位置，提升查找性能。可删除该语句。
if(temp[0][j]>a[max])break;//减少循环比较的次数。可删除该语句。
for(int i=0;i<j;i++){
if(temp[i][j]>a[max])break;//减少循环比较的次数。可删除该语句。
if(contains(temp[i][j],a,index)){
System.out.println(a[i]+" + "+a[j]+" = "+temp[i][j]);
}
}
}
} /**
* 从数组a中查找是否存在n的值，起始位置是index。
*/
private static boolean contains(int n, int[] a, int index) {
for(;a[index]<=n;index++){
if(a[index]==n)return true;
if(a[index]>n)return false;
}
return false;
}}

算法的时间复杂度和空间复杂度，我忘了怎么算了。
因为有System.out.println()语句，所以会影响到这个结果输出的时间，毕竟属于IO操作。

下面是我刚得到的结果，里面有个有意思的规律：
从数组中取出任意三个点(a, f(a)), (b, f(b)), (c, f(c)),其中f(b) = f(a) + f(c)
在二维坐标系统中，以下四个点构成一个矩形：
(a, 0), (a, f(b)), (c, 0), (c, f(b))
而等式f(b) = f(a) + f(c)在这个矩形中的意思就是：
过二点(a, f(a)), (b, f(b))的直线也必须过这个矩形的中心！否则f(b) = f(a) + f(c)就不会满足

看看一个BABY提供的思路：
三角形两边和一定大于第三边。
如果相等就在一条线段上！

想不出复杂度是 O(nlog(n)) or O(n^2) 的算法，惭愧。。

我把我写的代码发上来吧
但是我测了时间的，超级慢的...
而且代码本身还有错误，我还没有调好，因为自己也是初学，所以不能在一题上投入太多时间，还是学新知识要紧，
不写了，下面是我的代码，能得到结果，但是有逻辑错误/**未完成2008年11月25日18：55，想了两天了，做了一下午了...还是做不出来，
* 20:52，决定不做了...以后再说，这样下去只是浪费时间
* 这代码写的，越来越不面向对象了...而且弄的越来越复杂！
* 算法题
* A为整数数组,长度N，求最大的A[i]，使得A[i]=A[x]+A[y].
* 0 <=i,x,y <N
*算法的复杂度是 O(nlog(n)) or O(n^2)
* */
package csdn.question.myanswer;import java.util.*;class Point {
double x;
double y;

Point(double x, double y) {
this.x = x;
this.y = y;
}
}class Line { //直线
Point startP;
Point endP ;
double middlePointX;//直线中点的横坐标

Line(Point p1, Point p2) {
startP = p1;
endP = p2;
middlePointX = (endP.x - startP.x) / 2 + startP.x;
}

boolean inLine(Point p) {//判断p是否在Line上
boolean in;
in = ((startP.y - p.y) / (startP.x - p.x) ==
(startP.y - p.y) / (startP.x - p.x));

if(in) {
return true;
} else {
return false;
}
}

double distanceMiddlePoint(Point p) {//计算p与直线中点的横向距离 return Math.abs(p.x - middlePointX);
}
}public class MaxIsSumOfOtherTwo {

public static void main(String[] args) {
long s = System.nanoTime();
int[] arr = {5, 8, 3, 1, 2, 7, 4, 9, 50, 51, 49, 100};

int i, j, temp;
for (i = 1; i < arr.length; i++) {
j = i;
temp = arr[j];
//局部排序
while(j > 0 && temp > arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}

temp = arr[0];
int[] newArr = new int[temp];//生成新的数组，此数组用来"画"直线（抽象的，脑袋里的）
for (int k = 0; k < newArr.length; k++) {
newArr[k] = temp;
temp--;
}

// int[] aa = new int[arr.length];//标记arr中的数在newArr中的位置
// for (int k = 0; k < arr.length; k++) {
// for (int index = 0; index < newArr.length; index++) {
// if(arr[k] == newArr[index]) {
// aa[k] = index;
// }
// }
// }

boolean breakSign = false;
//开始找
for (int k = 0; k < newArr.length; k++) {
Point p1 = new Point(k, newArr[k]); //直线起点
Point p2 = new Point(newArr.length, 0);//直线终点
//思路是：已经从大到小排好了，从左到右一个个查找，如果第一次找到，就得到答案了
//如何找：作一条直线(当然不用画出来),它的起点是下标为k的那个点(k, arr[k])
//它的终点是(arr.length, 0),这样可以想象出一个直角三角形吧?!而且这个直线一定
//过矩形中点(关于矩形中点我在45楼论证过)..
Line line = new Line(p1, p2);
for (int index = k + 1; index < newArr.length; index++) {
Point p = new Point(index, newArr[index]);
if(!line.inLine(p)) {//不在直线上的点不判断
continue;
}
int m = (int)(line.middlePointX + line.distanceMiddlePoint(p));

boolean inArr = false;//在newArr中的数是否在arr中
for (int x = 0; x < arr.length; x++) {
if(arr[x] == newArr[index]) {
inArr = true;
break;
}
}

if(inArr &&
newArr[m] == newArr[k] - newArr[index]) {
System.out.println(newArr[m] +
"+" + newArr[index] + "=" + newArr[k]);
breakSign = true;
break;
}
}
if(breakSign){
break;
}

}
//查找结束

long e = System.nanoTime();
System.out.println((e - s));
for (int k : newArr) {
System.out.print(k + " ");
}
}
}

这个可能是O（n^n）吧？
          public static void main(String[] args) {
int[] numbers = {4, 4, 5, 0, 1, 2, 3, 8, 9, 9, 100 }; Arrays.sort(numbers);
for(int i=numbers.length-1;i>=2;i--){
   int a = 0;
   int b = i-1;
   while(a<b){
      if(numbers[a]+numbers[b] == numbers[i]){
            System.out.println(numbers[a]+"+"+numbers[b]+"="+numbers[i]);
            System.exit(0);
      }
      else if(numbers[a]+numbers[b] > numbers[i]){
--b;
      }
      else if(numbers[a]+numbers[b] < numbers[i]){
++a;
      }
   }
} System.out.println("no this number!");
}

如果是N^N的话我这个代码少一点.....虽然排序的时间复杂度和找的复杂度是相加的，到时取复杂度高的那个。但快排最差情况就O(N^N)了.... 所以我这个肯定是O(N^N)了 55555555555伤心中

看了你们研究的什么矩阵的感觉这道题应该要很复杂的数学方法求到NLN2
等NLN2的算法

public static void main(String[] args) {
int[] numbers = {4, 4, 5, 0, 1, 2, 3, 8, 9, 9, 100 }; Arrays.sort(numbers);
for(int i=numbers.length-1;i>=2;i--){
  int a = 0;
  int b = i-1;
  while(a <b){
      if(numbers[a]+numbers[b] == numbers[i]){
            System.out.println(numbers[a]+"+"+numbers[b]+"="+numbers[i]);
            System.exit(0);
      }
      else if(numbers[a]+numbers[b] > numbers[i]){
             --b;
      }
      else if(numbers[a]+numbers[b] < numbers[i]){
             ++a;
      }
  }
} System.out.println("no number!");
}
不好意思上面写错了

我的算法时复是   n^2 =n*n   写成了 n^n了，一看吓了一跳   要慢死了

首先，我们要取得最大的那个数A［i］,是取得它，用到shell的复杂度是O(nlog(n)) ，用冒泡的是 O(n^2)
我们要去做A[i]=A[x]+A[y]这个，把他变换成：A[i]-a[j]=a[j-1](j=i-1)，一共进行多少次比较这里就是用数学里的求和公式sigma求出来
所以算法的复杂度不可能是O(nlog(n)) or O(n^2) 没时间写程度了。
写一下思路吧。
1.用冒泡排序，走一趟后，得到一个最大的，A［i］
2,求A［i］-A［i-1］=A[j],遍历胜下的，要是找到等于A[j],则推出，否则重复2。一直递归下去。

我能想出的算法的复杂度为算法：
1、排序，复杂度 O(n logn)
2、查找，复杂度 O(n ^ 2 logn)
for (int i=n;i>=3;i--){
  // O(n)
  for (int j=i-1;j>=2;j--){
     // O(n)
     int z=a[i]-a[j];   //计算差值
      // O(logn)
      binarySearch(a,z,0,j-1);  //在j下面的数组中二分查找
  }
}
总的复杂度：O(n ^ 2 logn)

package max;public class MaxNumber
{
private int n=10;
private int[] array=new int[n];
public MaxNumber()
{
int[] arr={3,5,1,9,4,10,45,34,23,7};
array=arr;
InsertSort(arr,0,9);//先用插入排序排序;
for(int i=9;i>=0;i--)//从最大值开始找起;
{
for(int j=9;j>=0;j--)
{
for(int k=0;k<10;k++)
{
if(arr[i]==arr[j]+arr[k])
{
System.out.println(arr[i]);//找到后退出！
System.exit(0);
}
}
}

}
}
    public void InsertSort(int Item[],int l,int r)
{
int min=Item[l];
for(int i=l+1;i<r;i++)
{
if(min>Item[i])
{
min=Item[i];
}
}
for(int i=l;i<r;i++)
{
if(Item[i]==min)
{
Item[i]=Item[l];
Item[l]=min;
break;
}
}
for(int i=l+2;i<=r;i++)
{
int j=i;
int v=Item[i];
while(v<Item[j-1])
{
Item[j]=Item[j-1];
j--;
}
Item[j]=v;
}
}

public static void main(String args[])
{
new MaxNumber();
}
}

package max;public class MaxNumber
{
private int n=10;
private int[] array=new int[n];
public MaxNumber()
{
int[] arr={3,5,1,9,4,10,45,34,23,7};
array=arr;
InsertSort(arr,0,9);//先用插入排序排序;
for(int i=9;i>=0;i--)//从最大值开始找起;
{
for(int j=9;j>=0;j--)
{
for(int k=0;k<10;k++)
{
if(arr[i]==arr[j]+arr[k])
{
System.out.println(arr[i]);//找到后退出！
System.exit(0);
}
}
}

}
}
    public void InsertSort(int Item[],int l,int r)
{
int min=Item[l];
for(int i=l+1;i<r;i++)
{
if(min>Item[i])
{
min=Item[i];
}
}
for(int i=l;i<r;i++)
{
if(Item[i]==min)
{
Item[i]=Item[l];
Item[l]=min;
break;
}
}
for(int i=l+2;i<=r;i++)
{
int j=i;
int v=Item[i];
while(v<Item[j-1])
{
Item[j]=Item[j-1];
j--;
}
Item[j]=v;package max;public class MaxNumber
{
private int n=10;
private int[] array=new int[n];
public MaxNumber()
{
int[] arr={3,5,1,9,4,10,45,34,23,7};
array=arr;
InsertSort(arr,0,9);//先用插入排序排序;
for(int i=9;i>=0;i--)//从最大值开始找起;
{
for(int j=9;j>=0;j--)
{
for(int k=0;k<10;k++)
{
if(arr[i]==arr[j]+arr[k])
{
System.out.println(arr[i]);//找到后退出！
System.exit(0);
}
}
}

}
}
    public void InsertSort(int Item[],int l,int r)
{
int min=Item[l];
for(int i=l+1;i<r;i++)
{
if(min>Item[i])
{
min=Item[i];
}
}
for(int i=l;i<r;i++)
{
if(Item[i]==min)
{
Item[i]=Item[l];
Item[l]=min;
break;
}
}
for(int i=l+2;i<=r;i++)
{
int j=i;
int v=Item[i];
while(v<Item[j-1])
{
Item[j]=Item[j-1];
j--;
}
Item[j]=v;
}
}

public static void main(String args[])
{
new MaxNumber();
}
}

}
}

public static void main(String args[])
{
new MaxNumber();
}
}

体验一下!

算法：数组第一个值与后面的值分别相加，查看数组中是否存在结果
代码如下：public class TestAdd {

static int count = 0;

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1,4,8,9,5,0};
for(int i = 0;i < a.length;i++) {
int j = i + 1;
while(j < a.length) {
int sum = a[i] + a[j];
for(int k = 0 ;k < a.length;k++) {
if(sum == a[k]) {
System.out.println(a[i] + " + " + a[j] + " = " + a[k]);
count = count + 1;
}
}
j = j + 1;
}
}
if(count == 0) {
System.out.println("There is no data fit!");
} else {
System.out.println("There is " + count + " records fit!");
}
}}

O(n ^ 2 logn)
当n>=2时，它就超出了O（n^2）的范围了

我觉得如果要O(n*n)，应该还有其他先决条件，比如数字不能重复
输入：{ 4, 4, 5, 0, 1, 2, 3, 8, 9, 9, 100 }
这种输入不太可能

忘记C怎么写了
java.....public static void main(String[] args){
int[] a = new int[]{1,2,3,4,5,6,7,8,3000};
int max=0;
int len= a.length;
                //求最大值
for(int i=0;i<len;i++){
if(a[i]>max){
max=a[i];
}
}
int[] b=new int[max+1];
                //求所有可能的和,大于最大数的丢弃
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
if(a[i]+a[j]==max){
System.out.println(max+" is max");
return;
}else if(a[i]+a[j]<max){
b[a[i]+a[j]]=1;
}
}
}
int result =-1;
                //判断数组中是否有数字等于其它两数的和,取最大的.
for(int i=0;i<len;i++){
if(b[a[i]]==1){
if(a[i]>result){
result=a[i];
}
}
}
System.out.println(result);
}

public class TestNode
{
public int[] sort(int[] a)
{
int temp;
for(int i=0;i<a.length-1;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
return a;
}
public int display(int[] a)
{
int front=0,rear;
for(int j=a.length-1;j>=2;j--)
{
rear=front+1;
while(rear<=j-1)
{
while(a[front]+a[rear]!=a[j] && rear<=j-1&&a[front]+a[rear]<a[j])
{
rear++;
System.out.println(rear-1);
}
if(!(a[front]+a[rear]>a[j]) && rear<=j-2)
{
System.out.println(a[front]+"+"+a[rear]+"="+a[j]);
return 0;
}
else
{
front++;
rear=front+1;
}
}
front=0;
}
return -1;

}
public int exist(int a[],int value)
{
for(int k=0;k<a.length;k++)
{
if(a[k]==value)
return k;
}
return -1;
}
public static void main(String args[])
{
TestNode t=new TestNode();
int a[]={9,7,8,3,4,1,12,14,16,7,8,9,0,6,50,56,23,25,26,31,23,45,19,28,41,42,43,44,45,46,47,48,49,25,26,27,28,29,31,36,35,38,45,61,64,10,11,9};
int b[]=t.sort(a);
int dis=t.display(b);
if(dis==-1)
System.out.println("没有所要求的情况");
}
}

嘿嘿，我这个有计数的，所有的比较赋值都算一个操作
看看复杂度好像很小啊package my;import java.util.Arrays;public class TestAdd {
    public static void main(String[] args) {
        int[] a = {5,9,7,3,6,4,8,1,0,12,15,6,4,4};
        System.out.println(find(a));
        int[] b = {5,4,1,2,3};        //最好情况
        System.out.println(find(b));
        int[] c = {5,4,2,3};
        System.out.println(find(c));
        int[] d = { 5, 8, 3, 1, 2, 4, 4 };
        System.out.println(find(d));
        int[] e = { 1,1,1,1,1,1,1,1}; //最坏情况
        System.out.println(find(e));
    }

    public static String find(int[] a) {
        final boolean isBigModel = false;  //切换运行模式(有效率上的差异)
        int count = 0; //计数运算次数
        Arrays.sort(a);
        for (int i : a) {
            System.out.print(i+" ");
        }
        //i为数组最右边，即从最大的元素开始
        for(int i=a.length-1 ;i > 1; i--){
            //j,k分别为查找时的左右游标
            for(int k = i-1 ; k > 0 ; k--){
                if(isBigModel){
                    count++;
                    if(a[k]+a[k-1]<a[i]) //如果倒数2，3大的数相加都没有i的大，跳过
                        continue;
                }
                for (int j = 0; j < k; j++) {
                    if(isBigModel){
                        count++;
                        if (a[j] + a[k] > a[i]) //如果大于了，跳过
                            break;
                    }
                    count++;
                    if (a[j] + a[k] == a[i])
                        return "Result is :" + a[j] + "+" + a[k] + "=" + a[i] +
                                "  count:" + count + "/" + a.length;
                }
            }
        }

        return "No Results!" + "  count:" + count + "/" + a.length;
    }
}
结果1：
Is Big Model ? --false
0 1 3 4 4 4 5 6 6 7 8 9 12 15 Result is :3+12=15  count:3/14
1 2 3 4 5 Result is :1+4=5  count:1/5
2 3 4 5 Result is :2+3=5  count:3/4
1 2 3 4 4 5 8 Result is :3+5=8  count:3/7
1 1 1 1 1 1 1 1 No Results!  count:56/8   --  8*8=64
结果2（大模式运行）：
Is Big Model ? --true
0 1 3 4 4 4 5 6 6 7 8 9 12 15 Result is :3+12=15  count:7/14
1 2 3 4 5 Result is :1+4=5  count:3/5
2 3 4 5 Result is :2+3=5  count:5/4
1 2 3 4 4 5 8 Result is :3+5=8  count:7/7
1 1 1 1 1 1 1 1 No Results!  count:42/8大家可以跑一下，用你们可以找的的最耗时的数组

又研究了下，不算快速排序的损耗，比n^2好像在无限接近中，郁闷Is Big Model ? --true0 1 3 4 4 4 5 6 6 7 8 9 12 15 Result is :3+12=15  count:7/14
1 2 3 4 5 Result is :1+4=5  count:3/5
2 3 4 5 Result is :2+3=5  count:5/4
1 2 3 4 4 5 8 Result is :3+5=8  count:7/7
0 1 2 3 4 4 5 8 9 9 100 Result is :0+9=9  count:12/11  --这个也不耗时嘛1 No Results!  count:0/1
1 1 No Results!  count:0/2
1 1 1 No Results!  count:2/3
1 1 1 1 No Results!  count:6/4
1 1 1 1 1 No Results!  count:12/5
1 1 1 1 1 1 No Results!  count:20/6
1 1 1 1 1 1 1 No Results!  count:30/7
1 1 1 1 1 1 1 1 No Results!  count:42/8
1 1 1 1 1 1 1 1 1 No Results!  count:56/9
1 1 1 1 1 1 1 1 1 1 No Results!  count:72/10
这个什么规律我看不出，我数学差，哪个可以做出这个的函数来？
No Results!  count:9702/100
No Results!  count:997002/1000
No Results!  count:99970002/10000

解决方案 »