배열 정렬, 컬렉션을 사용하여 배열 목록 정렬

Question

그래도 여전히 배열을 배우고 있습니다. "rand"라는 배열을 0에서 1 사이의 임의의 숫자로 채우는이 코드를 작성했습니다. 복잡성을 배우기 시작하겠습니다. For 루프는 O (1) 시간이 걸릴 때마다 n 번 (100 번) 실행되므로 최악의 시나리오는 O (n)입니다. 맞습니까? 또한 100 개 요소를 저장하기 위해 ArrayList를 사용하고 "Collections"를 가져오고 Collections.sort() 메서드를 사용하여 요소를 정렬했습니다.

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)); 
     } 

    } 
} 

Answer 1

예 당신이 올바른지, 추가 N 항목의 복잡도는 O (N). 워드 프로세서에 의한 대부분의 경우 부가적인 O 걸릴 정렬 (N의 * 로그 (N))

소트 알고리즘은 존 L. 벤틀리 M. 더글라스 맥 일로이의 "엔지니어링 구성된 튜닝 퀵이며 함수 정렬 ", 소프트웨어 - 연습 및 경험, Vol. 23 (11) P. 1249-1265 (November 1993). 이 알고리즘은 많은 데이터 집합 에서 n * log (n) 성능을 제공하므로 다른 퀵 소트가 2 차 성능으로 저하됩니다.

ArrayList은 여전히 ​​배열에 의해 뒷받침되므로 복잡성은 동일합니다. 어쨌든 크기를 조정할 수있는 경우가 있습니다.