240125_복잡도&선형자료구조_김현욱

[Hyeon-Uk]

1. 아래의 코드의 시간복잡도를 구하는 과정을 적어주세요

Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextInt());
int[] arr = new int[n];
for(int i=0; i<n; i++) {
 for(int j=i+1;j<n;j++) {   
  if(arr[i] > arr[j]){
   int temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
}

답 : O(n^2) 1+2+3+4+....+n 의 등차수열이다. 이는 n×(n+1)/2가 되기때문에 n^2/2 + n/2가 되기때문에, 상한인 O(n^2) 이 된다.

2. 배열의 특징 3가지와 접근, 탐색, 삽입, 삭제의 시간복잡도를 말해주세요.

답 : 1. 배열은 데이터를 인접한 메모리에 순차적으로 저장한다. 2. 고정된 크기로 할당이 된다. 3. 직접 접근(랜덤 접근) 이 가능하다.

접근: O(1)
탐색 : O(n)
삽입 : O(n)
삭제 : O(n)

3. 리스트의 특징 3가지와 접근, 탐색, 삽입, 삭제의 시간복잡도를 말해주세요. 단 삽입과 삭제는 해당 노드의 위치를 안다고 가정합니다.

답 : 1. 리스트는 데이터를 노드의 논리적인 연결을 통해 순차적으로 저장한다. 2. 크기가 고정되어있지 않다.. 3. 직접 접근(랜덤 접근) 이 불가능하고 순차 접근만 가능하다.

접근: O(n)
탐색 : O(n)
삽입 : O(1)
삭제 : O(1)

4. ArrayList와 LinkedList의 차이점을 말해주세요. 어느 상황에서 어떤 자료구조를 사용하면 좋은지도 말해주세요.

답 : ArrayList는 내부적으로 배열을 사용한 List 구현체입니다. 내부적으로 배열을 사용하기 때문에 배열의 크기 이상으로 데이터가 추가된다면, 해당 배열의 크기에서 더 늘린 크기의 배열을 할당한 뒤, 데이터를 복사한다음 새로운 데이터를 추가합니다. 또한 배열을 이용하기 때문에 접근에 유리합니다. 이런 ArrayList는 데이터의 크기를 유추할 수 있거나, 추가 또는 삭제 작업보단 조회를 하는 작업이 많은 서비스에 유리합니다.

LinkedList는 노드간 연결을 이용한 List 구현체입니다. 따라서 데이터가 계속 추가된다해도 추가적인 작업(배열을 늘린 뒤, 복사하여 추가와 같은 작업)이 없기때문에 데이터의 크기를 유추할 수 없는 작업에 유리하며, 조회보다는 삽입, 삭제, 특히 맨 뒤 혹은 맨 앞에 추가/삭제 작업이 많은 서비스에 유리합니다.

[qudtjs0753]

1. 아래의 코드의 시간복잡도를 구하는 과정을 적어주세요

Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextInt());
int[] arr = new int[n];
for(int i=0; i<n; i++) {
 for(int j=i+1;j<n;j++) {   
  if(arr[i] > arr[j]){
   int temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
}

답 : $O(n^2)$
i=0 -> j=1~n ->n
i=1 -> j=2~n -> n-1
...
i=n-1 -> j=n -> 0
$n-1 + n-2 + ... + 1 + 0 = n(n-1)/2$ -> $O(n^2)$

2. 배열의 특징 3가지와 접근, 탐색, 삽입, 삭제의 시간복잡도를 말해주세요.

답 :

배열 특징

1. random access
2. fixed size
3. 논리적으로는 연속적(단, 물리적 메모리 주소는 연속적이지 않을 수 있다)

시간복잡도

접근, 수정 $O(1)$
삽입, 탐색,삭제 $O(1)$

3. 리스트의 특징 3가지와 접근, 탐색, 삽입, 삭제의 시간복잡도를 말해주세요. 단 삽입과 삭제는 해당 노드의 위치를 안다고 가정합니다.

답 :

특징

1. sequential access만 가능.
2. 논리적으로도 불연속적으로 저장. 참조를 활용한다고 보면 된다.
3. 사이즈가 딱히 정해져있지 않다. 새로 이어나가기만 하면 된다.

시간복잡도

접근, 탐색 : $O(n)$
삽입, 삭제 : $O(1)$

4. ArrayList와 LinkedList의 차이점을 말해주세요. 어느 상황에서 어떤 자료구조를 사용하면 좋은지도 말해주세요.

답 :
- ArrayList는 배열을 사용. LinkedList는 리스트 사용. 즉, ArrayList는 크기 설정 없이도 잘 동작하지만 내부적으로 배열 사이즈를 늘려서 복제하는 로직이 있다고 보면 된다.
- 시간복잡도 측면에서 삽입이나 삭제가 많은 경우 LinkedList를. random access로 접근하는 경우가 많다면 ArrayList를 사용하는 것이 좋다고 보면 된다.
특히 삽입 삭제가 일어날 때 크기가 한번에 많이 바뀌게 되면 내부적으로 배열을 사용하는 ArrayList의 경우 복제시간이 비효율적이기에 문제가 될 수 있다.
- 공간복잡도 측면에서 봤을때 LinkedList는 각 내부 구현에 따라 다르지만 이전 element와 다음 element에 대한 참조를 저장한다. 메모리상으로 손해가 존재.
ArrayList의 크기가 들쭉날쭉해지면 내부 구현에 따라 배열 사이즈가 널널하게 커지기때문에 또 손해가 될 수 있다.
배열 사이즈가 얼마나 많이 바뀌는가가 관건