java - 使用分而治之的反转计数

Question

我正在尝试实现一个计算反转次数的程序，但它不适用于大输入大小(100,000)。

未排序的数字是从一个 txt 文件中挑选出来的。该程序适用于 10 或 15 甚至 20 等小输入尺寸。

但是当我从这个链接复制输入时:http://spark-public.s3.amazonaws.com/algo1/programming_prob/IntegerArray.txt该程序只持续运行几秒钟而没有产生任何输出。

我使用了基于归并排序的分而治之算法，并在BlueJ中实现。

这是代码。

import java.util.*;
import java.io.*;
class INVERSION
{
 private static LinkedList<Integer>arr;
 private static Scanner s;
 private static long count=0;
 public static void count_inv(int low,int high)
 {
     if(high<=low)
      return ;
     else
     {
         int mid= low + (high-low)/2;
         count_inv(low,mid);
         count_inv(mid+1,high);
         split_inv(low,high);

     }
 }
 public static void split_inv(int low,int high)
 {
     int mid=low+ (high-low)/2;
     int i=low,j=mid+1;
     int k=0;
     int []aa=new int[high-low+1];
     while(i<=mid&&j<=high)
     {
         if(arr.get(i)<=arr.get(j))
          aa[k++]=arr.get(i++);
         else {count+=mid-i+1; aa[k++]=arr.get(j++);}
     }
     while(i<=mid)
      aa[k++]=arr.get(i++);
     while(j<=high)
      aa[k++]=arr.get(j++);
     for(int e:aa)
      arr.set(low++,e);

 }
 public static void main(String []args)throws IOException
 {
  BufferedReader br=new BufferedReader(new FileReader("JJ.txt"));
  arr=new LinkedList<Integer>();
  String s="";
  while((s=br.readLine())!=null)
   arr.add(Integer.parseInt(s));                
  count_inv(0,arr.size()-1);
  System.out.println("the number of inversions is "+count);   
 }
}

Answer 1

我认为问题可能出在您使用的是 LinkedList。

随机访问的访问时间为 O(n)。

您进行了 O(nlogn) 次访问，因此总的来说您的时间将是 O(n^2logn)。

尝试只使用普通数组，或使用其他访问时间为 O(1) 的数据结构，例如 ArrayList。