서론

수업 시간동안 알게 된 메서드의 기능 및 시간복잡도에 대해 알아보자.

Arrays 메소드

method	기능	시간복잡도
copyOf(arr, copyArrayLength)	배열 전체를 복사해 복사한 길이만큼 지정해 복사한 새로운 배열로 반환	O(N)
copyOfRange(arr, sIdx, eIdx)	배열 시작 인덱스와 끝 인덱스를 지정하여 복사한 새로운 배열 반환	O(eIdx - sIdx)
fill(arr, n)	배열의 모든 요소를 동일한 값으로 채워준다.	O(N)
toStrign(arr)	배열을 문자열로 변환하여 반환한다.	O(N)
sort(arr)	배열내의 요소들을 오름차순으로 정렬한다.	O(NlogN) ~ O(N^2) 냅적으로 퀵 정렬 ( DualPivotQuicksort.sort() ) 을 사용한다.
equals(arr1, arr2)	두 배열의 각각의 요소 값이 동일한지 비교하여 true/false 를 반환한다.	O(N)
deepEquals(arr1, arr2)	단일 차원 또는 다차원 배열인 두 배열이 같은지 비교하여 true/false 를 반환한다.	?
binarySearch(arr, idx)	이진 탐색을 사용해 해당 위치를 반환한다. 단, 미리 정렬되어있어야 한다.	O(logN)

DualPivotQuicksort 은 삽입 정렬과 퀵 정렬을 섞은 형태로 두개의 pivot 을 사용하여 그냥 퀵 정렬보다 성능이 좋다.

다만 인자의 타입이 원시타입일 경우 sort() 는 DualPivotQuickSort.sort() 를 사용하고 객체 타입인 경우 삽입 정렬과 병합 정렬을 섞은 TimSort.sort() 를 사용한다.

TimSort - O(NlogN) 의 성능을 보이며 O(N^2) 인 퀵 정렬보다 효율적이다. 기존 병합 정렬보다 추가 메모리를 적게 사용한다.

deepEquals 메서드의 시간복잡도는 두 다차원 배열을 비교할 때에 따라 달라질 수 있다. 그리고 실제 구현에 따라 시간 복잡도가 달라질 수 있으니 해당 메서드의 시간 복잡도를 구체적으로 명시하기 어렵다.

예제

package com.example.kdt8.w2.배열;

import java.util.Arrays;
import java.util.Comparator;

public class ArrayMethodStudy {
  public static void main(String[] args) {
    int[] arr = {0, 1, 2, 3, 4};

    // copyOf(arr, copyArrayLength)
    int[] newArr1 = Arrays.copyOf(arr, arr.length);
    System.out.println(Arrays.toString(newArr1));

    int[] newArr2 = Arrays.copyOf(arr, 3);
    System.out.println(Arrays.toString(newArr2));

    // 본인 크기보다 더 넓은 범위로 두 번째 인자를 전달하면 0으로 채워진다.
    int[] newArr3 = Arrays.copyOf(arr, arr.length + 3);
    System.out.println(Arrays.toString(newArr3));

    // copyOfRange - 중간 특정 인덱스 범위만 복사
    int[] newArr4 = Arrays.copyOfRange(newArr3, 1, 4);
    System.out.println(Arrays.toString(newArr4));

    // fill - 배열을 특정 요소들로 채운다.
    int[] fillArr1 = new int[5];
    Arrays.fill(fillArr1, 0);
    System.out.println(Arrays.toString(fillArr1));

    // fill 에서 특정 인덱스 부터 끝 인덱스까지 특정 요소들로 채워줄 수 있다.
    int[] fillArr2 = new int[5];
    fillArr2[0] = 1;
    fillArr2[1] = 1;
    fillArr2[2] = 1;
    Arrays.fill(fillArr2, 3, fillArr2.length, 100);
    System.out.println(Arrays.toString(fillArr2));

    // sort - 오름차순
    int[] sortArr1 = {0, 100, 1, 2, 321, 4001, 10030, 4200};
    Arrays.sort(sortArr1);
    System.out.println(Arrays.toString(sortArr1));

    // sort - 내림차순 => Comparator 사용하기 위해서는 int 가 아닌 Integer 같은 Wrapper 를 사용해야 한다.
    Integer[] sortArr2 = {0, 100, 1, 2, 321, 4001, 10030, 4200};
    Arrays.sort(sortArr2, Comparator.reverseOrder());
    System.out.println(Arrays.toString(sortArr2));

    // equals
    int[] equalArr1 = { 1, 2, 3, 4};
    int[] equalArr2 = { 1, 2, 3, 4};
    int[] equalArr3 = { 1, 3, 2, 4};
    int[] equalArr4 = { 1, 2, 3, 4, 5};

    System.out.println(Arrays.equals(equalArr1, equalArr2));
    System.out.println(Arrays.equals(equalArr1, equalArr3));
    System.out.println(Arrays.equals(equalArr1, equalArr4));

    // deepEquals
    int doubleArr1[][] = {{1, 2}, {3, 4}, {5, 6}};
    int doubleArr2[][] = {{1, 2}, {3, 4}, {5, 6}};
    int doubleArr3[][] = {{1, 3}, {5, 4}, {7, 6}};

    System.out.println(Arrays.deepEquals(doubleArr1, doubleArr2));
    System.out.println(Arrays.deepEquals(doubleArr1, doubleArr3));

    // binarySearch
    System.out.println(Arrays.binarySearch(equalArr4, 3));
  }
}

ArrayList 메소드

크기를 미리 정하지 않아도 되는 배열, 동적 할당시 유용하다.

method	기능	시간복잡도
add(element)	ArrayList 맨 뒤에 element 추가	O(1)
add(index, element)	index 위치에 element 삽입	O(N)
addAll(ArrayList)	ArrayList 뒤에 ArrayList 추가	O(n + m) n, m 은 각각 ArrayList 의 size
size()	ArrayList 의 길이 리턴	O(1)
get(index)	index 에 해당하는 요소 리턴	O(1)
indexOf(params)	params 와 같은 첫 번째 요소의 index 를 리턴하며 없으면 -1 을 리턴한다. 배열 전체를 순회해야 해서 O(N) 이다.	O(N)
remove(index)	index 의 요소를 삭제한다.	O(N)
remove(value)	앞에서부터 동일한 객체를 찾고 이후 remove(index) 와 동일하다	O(N)
clear()	모든 요소를 삭제한다.	O(N)

ArrayList 는 중간, 앞부분에서 데이터를 추가, 삭제하는 경우 항상 O(N) 이다. 줄서기를 생각해보면 누군가 새치기를 하거나 줄서기를 포기하면 나머지 사람들이 모두 위치를 바꿔줘야 해서 추가, 삭제에 O(N) 이 소요된다. 그러나 누군가를 찾을 때는 해당 인덱스로 바로 가면 되니 검색은 O(1) 이다.

예제

package com.example.kdt8.w2.배열;

import java.util.ArrayList;

public class ArrListStudy {
  public static void main(String[] args) {
    ArrayList<Integer> arrList1 = new ArrayList<>();
    ArrayList<String> arrList2 = new ArrayList<>();

    arrList1.add(10);
    arrList1.add(8);
    arrList1.add(6);
    arrList1.add(4);
    arrList1.add(0, 1);

    // addAll
    ArrayList<Integer> arrList3 = new ArrayList<>();
    arrList3.add(1);
    arrList3.add(2);
    arrList1.addAll(arrList3);

    // remove
    arrList1.remove(0);

    // indexOf - 리스트에 특정 요소가 존재하는지 여부를 확인할 수 있다.
    System.out.println(arrList1.indexOf(1)); // 여러개 있을때 처음 등장한 요소의 인덱스 반환
    System.out.println(arrList1.indexOf(12)); // 없으면 -1 반환

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

    arrList1.clear();
    System.out.println("arrList1.size() : "+arrList1.size());

  }
}

레퍼런스

reference
ArrayList - addAll() time complexity
ArrayList - clear() time complexity