[자료구조] Unsorted/Sorted Lists(미정렬/정렬 리스트), Time Complexity(시간 복잡도)

*개인 학습 목적으로 정리한 글입니다. 오류가 있다면 부담없이 지적해주세요, 감사합니다.*

 

Unsorted Lists를 한국어로 어떻게 번역하는지 잘 모르겠다…

아시는 분은 댓글로 알려주세요 ㅠ

 

1. List 

- 선형 관계

앞 요소 == 전임자(predecessor)

뒤 요소 == 후임자(successor)

—-> 당연하게도 첫 요소는 전임자가 없고, 마지막 요소는 후임자가 없음

 

- 길이

리스트 안의 아이템 수는 변할 수 있음! (Array와의 차이점)

ex) append, remove…

---

2. Unsorted List

- 아이템들이 특정 순서 없이 임의로 놓여진 리스트

- Python의 <list>

 

2.1. 기본 ADT 연산

Constructor(생성자):  ADT의 새로운 인스턴스 생성

-  클래스 오브젝트가 생성될 때 자동으로 호출되는 멤버 함수

- 값을 리턴하지 않으며, 리턴 타입을 갖지 않음

리턴 타입이 없다

- 한 클래스는 여러 개의 생성자를 가질 수 있음(파라미터의 조합들에 따라)

- 파라미터가 없는 생성자가 기본임

Transformer ---> change data:  인스턴스 속 하나 이상의 값을 변경

Observer ---> observe data: 바꾸지 않고 데이터 값을 관찰

Q. appendItem과 insertItem의 차이점은?

 

public method 형태로 존재

append와 insert 정도는 스스로 구현해보기~

---

3. 시간 복잡도(Time Complexity)

 

appendItem()과 insertItem() 중 뭐가 더 빠를까?

직관적으로 생각하더라도 당연히 append다.

왜? 그냥 뒤에 붙이면 되거든 ㅋ

—-> 즉, 연산이 적을수록 빠르다.

 

하지만 좀 더 논리적으로 둘의 속도를 비교할 수 없을까?

연산의 수를 대략 추측할 수 있다면 더 효율적인 알고리즘/프로그램을 취할 수 있을 것이다.

 

3.1. Big-O

효율을 계산할 때는, 최악의(즉 가장 연산이 많은) 경우를 가정하는 것이 일반적이다.

 

appendItem(): 항상 2번의 연산

insertItem(): 리스트의 길이와 포지션(들어가야 할 위치)에 따라 다름

---> 최악의 경우 == 리스트의 길이가 n(무한)으로 늘어나고, 포지션이 0이 될 때

---> N + 1번의 연산이 필요

 

“최악의 경우를 가정할 때”

appendItem() —-> O(2) == O(1)

insertItem() —-> O(N+1) == O(N)

 

따라서 append쪽이 더 빠른 것!