[알고리즘] 시간 복잡도

 

코드트리에서 문제 풀다가 모르는 게 생겨서 지선생님께 여쭤봤다

까묵지말것

 

기본 개념

배열 값의 삽입 O(N)

배열 값의 삭제 O(1)

배열에서의 값 검색O(N)

K번째 원소 구하기 O(1)

---

1. 배열의 맨 뒤 데이터를 삭제하면 시간복잡도는 O(1)이 될 것이다.

정답: 맞음
설명: 배열의 마지막 데이터를 삭제하는 작업은 단순히 해당 데이터를 제거하면 되는 작업이므로 추가적인 데이터 이동이 필요하지 않습니다. 따라서 시간복잡도는 O(1)입니다.

---

2. 배열에서 특정 데이터를 맨 앞에 삽입하게 된다면 시간복잡도는 O(1)이 될 것이다.

정답: 틀림
설명: 배열의 맨 앞에 데이터를 삽입하면 기존의 모든 데이터를 한 칸씩 뒤로 이동시켜야 합니다. 이 작업은 배열의 크기에 비례하는 연산이 필요하므로 시간복잡도는 O(N)입니다.

---

3. 정렬되지 않은 배열에서 최댓값을 찾기 위해선 반드시 모든 값을 확인해야 한다.

정답: 맞음
설명: 정렬되지 않은 배열에서는 최댓값이 어디에 위치할지 예측할 수 없으므로 배열의 모든 값을 확인해야 합니다. 따라서 시간복잡도는 O(N)입니다.

---

4. 정렬된 배열에서 원하는 위치에 값을 삽입할 때의 시간복잡도는 O(N)이 될 것이다.

정답: 맞음
설명: 정렬된 배열에 값을 삽입하려면 값을 삽입할 위치를 찾아야 하고, 이후에도 기존 데이터를 뒤로 밀어야 할 수 있습니다. 삽입 위치를 찾는 데 O(log N)(이진 탐색) 시간이 걸릴 수 있지만, 데이터를 이동시키는 작업이 O(N)일 수 있으므로 전체적으로 O(N)의 시간복잡도를 가집니다.

---

5. 정렬되지 않은 배열에서 원하는 위치에 값을 삽입할 때의 시간복잡도는 O(N)이 될 것이다.

정답: 맞음
설명: 정렬 여부와 관계없이 배열의 특정 위치에 값을 삽입하면, 해당 위치 이후의 모든 데이터를 뒤로 이동해야 합니다. 이 작업은 배열 크기에 비례하므로 시간복잡도는 O(N)입니다.

---

6. k번째 원소 값을 구하기 위한 시간복잡도는 O(N)이 될 것이다.

정답: 틀림
설명: 배열은 인덱스를 통해 특정 원소에 즉시 접근할 수 있습니다. 따라서 k번째 원소를 가져오는 시간복잡도는 O(1)입니다. O(N)은 리스트처럼 선형 탐색이 필요한 자료구조에서 해당됩니다.