Sorting Array，Sorting ArrayList，using Collections

好的，仍在学习数组。我写了这个代码，填充名为“rand”的数组，其中0和1之间的随机数（独占）。我想开始学习复杂性。 For循环执行n次（100次），每次需要O（1）次，所以最坏的情况是O（n），对吗？此外，我用ArrayList来存储100个元素，我导入了“Collections”，并使用Collections.sort（）方法对元素进行排序。Sorting Array，Sorting ArrayList，using Collections

import java.util.Arrays; 
    public class random 
    { 
     public static void main(String args[]) 
     { 
      double[] rand=new double[10]; 

        for(int i=0;i<rand.length;i++) 
        { 
         rand[i]=(double) Math.random(); 
         System.out.println(rand[i]); 
        } 

        Arrays.sort(rand); 
        System.out.println(Arrays.toString(rand)); 
     } 
    }

的ArrayList：

import java.util.ArrayList; 
import java.util.Collections; 

public class random 
{ 
    public static void main(String args[]) 
    { 
     ArrayList<Double> MyArrayList=new ArrayList<Double>(); 


     for(int i=0;i<100;i++) 
     {    
      MyArrayList.add(Math.random()); 
     } 

     Collections.sort(MyArrayList); 


     for(int j=0;j<MyArrayList.size();j++) 
     { 
      System.out.println(MyArrayList.get(j)); 
     } 

    } 
}

来源

2012-09-01 user1639637

那么你的问题是什么？ – Tudor

是的，你是正确的，添加N项目的复杂度为O（N）。在大多数情况下，根据该文档排序将额外需要O（N *日志（N））：

排序算法是一个调谐快速排序，改编自乔恩L. 本特利和M.道格拉斯麦克罗伊的“工程一个排序功能“，软件 - 实践和经验，卷。 23（11）第1249-1265页（November 1993）。该算法在许多数据集上提供n * log（n）性能，导致其他快速排序降级为二次性能。

ArrayList仍然是一个数组的支持，所以复杂性将是相同的，因此，无论如何，偶尔会调整大小。

来源

2012-09-01 15:48:46 Tudor

Sorting Array，Sorting ArrayList，using Collections

回答

相关问题