💿 자료구조 - 빅오표기법과 Linked List

아이패드로 필기하면 걍 휘갈기고 낙서하길래 모든 과목을 맥북 필기로 하기류햇다

[ 빅오 표기법 ]

 

 

(21p~22p)

 ⭐️ 증가폭이 크다 = 시간복잡도가 크다 = 효율성이 낮다  ⭐️

시공할때 기억안나면 참고하라고 사진 껴놓음

{ 빅오 표기 찾는 간단한 방법 }

- n이 한없이 커질때

 - 최고차항만을 선택 -> 그 항의 계수 제거 -> 그게 g(n)이야

e.g.

복잡도 함수 O(n) = 2n^2 + 3n +5 -> 최고차항 is 2n^2 -> 계수제거시 n^2 -> 따라서 g(n) = n^2

 

{ 증가폭을 찾을 때 n에 숫자 대입하는 거 생각할 시에 뭐가 가장 중요할까요? }

- n이 엄~~청 클 때가 중요하다!!!! -n이 1,2 처럼 작을 때는 필요없긔요

 

---

 

[ 빅오메가 표기법 ]

 

---

[빅세타표기법]

 

---

 

 

알고리즘분석 하는 경우 : 최악의 경우(worst case) -수행시간이 가장 늦은 경우

 

 

[ 순차 탐색 ]  

- 정렬되지 않은 배열에서 어떤 값을 찾는 알고리즘

{최선의 경우}

: 맨 처음이 찾는 항목인 경우

T(n) = 1 -> O(1)

{최악의 경우} 

: 맨 마지막에 있거나 배열에 찾는 값이 없는 경우 

T(n) = n -> O(n)

{평균의 경우}

: 평균에 대한 가정이 필요

e.g. 배열의 모든 숫자가 골고루 한번씩 key로 사용되는 경우 :

      T(n)= (1+2+...+n) / n = n(n+1)/2 / n = (n+1) / 2

      T(n) = (n+1) / 2 -> O(n)

 

---

[ 리스트 ] = 동적배열

a = list() # = [] (다른 표현방식으로)

- 가장 자유로운 선형 구조 

- 순서를 가진 항목들의 모임

- 항목들은 "위치"(index)를 가짐

 

리스트 연산

- 삽입 & 삭제

 

[ 연산들의 시간 복잡도 ]

{배열의 "말단"에 데이터 추가}

- 데이터의 크기 n에 상관없이 마지막 위치에 추가하면 되므로 O(1)

{임의의 위치에 데이터 추가}

- 항목 이동 필요

- 데이터 크키 n에 영향을 받으므로 시간복잡도 is O(n)

{배열의 "말단"의 데이터 삭제}

- 다른 데이터에 영향을 주지 않으므로 O(1)

{임의의 위치의 데이터 삭제}

- 항목 이동 필요

- 데이터 크기 n에 영향을 받으므로 O(n)

 

[ 리스트 구현 방법 ]

<배열구조>

- 구현이 간단

- 항목 접근의 O(1) (=> 데이터의 위치(index)를 알고있기 때문)

 

<정적 배열>

-크기 고정

<동적 배열>

- 크기가 가변적임

- 배열의 크기가 부족해질 경우, 크기를 두배 늘리는 방식으로 데이터 제어

==> Q. 꽉 찬 정적배열에서 데이텇를 하나 더 말단에 추가하고자 할 떄의 시간복잡도는?

         A. 정적배열 -> 동적배열로 변환 후 데이터 추가 가능 (즉 용량 증가후 거따가 기존데이터를 복사, 붙여넣기)

             "복사붙여넣기"는 데이터 크기 n에 영향을 받으므로 O(n)

 

---

[ 연결형 자료구조 Linked List ]

- 각각의 다음 데이터를 가리키는 형태의 자료구조

 

node : 각각의 원소

 - 하나의 node는 data값과 next 대상을 가짐

    >> next는 다음 대상을 가리키지만,  다음 대상의 값을 알진 못한다 ( 나 다음은 너, 너 다음엔 누구? )

 

{ linked list에서 데이터를 삽입 }

- 어떤 위치에 데이터를 삽입하던, 다음 두과정만 거치면 됨

 1) 신규 node의 data와 next를 지정

 2) 직전 node의 next 대상을 신규 node로 변경

- 데이터 크기에 영향을 받지 않으므로, 시간복잡도는 O(1)

{ linked list에서 데이터를 삭제 }

- 어떤 위치의 데이터를 삭제하던, 다음 두 과정만 거치면 됨

 1) 삭제 대상(node) 직전 node의 next를 지정

 2) 삭제대상 node를 실제로 제거 

- 삭제 대상 직전 node를 이미 알고 있다면 O(1)

- 모른다면 최악의 상황, O(n) -> 이때의 해결책이 양방향 Linked List

 

 

 

[ 양방향 Linked List ] 

- 각각의 데이터가 이전 및 다음 데이터를 가리키는 형태의 자료구조

node : 각각의 원소

 - 하나의 node는 data값과 prev 및 next 대상을 가짐

 

{ 양방향 linked list에서 데이터를 삭제 }

- 어떤 위치의 데이터를 삭제하던 다음 3과정만

1) 삭제대상 데이터 직전 node의 next를 조정

2) 삭제 대상 데이터 직후 node의 prev를 조정

3) 삭제 대상 node를 실질적으로 제거

- 단방향 때와 달리, 삭제 대상 데이터 직전 node의 정보를 곧장 얻을 수 있음 ( 시간복잡도 = O(1) )

 

---

 

[ 클래스와 객체지향 ]

클래스 Class

인스턴스 - 클래스로부터 생성되는 각각의 개체들을 부르는 명칭

속성 - 각각의 인스턴스가 가질 수 있는 데이터 값

메소드 - 클래스 내에서 정의되고 사용되는 함수를 구분하여 일컫는 단어

---

 

[양방향 Linked List의 구현 ]

 

헤헷 내가 알아서 주석 써놓으면서 풀어봤는데 맞는듯 헤헤헷✌️

이해 완! - 시공 때 책에 있는 노드 그림이랑 같이 보면 더 이해 잘될듯요

https://github.com/codenameVien/DataStructure/blob/main/LinkedList.ipynb

DataStructure/LinkedList.ipynb at main · codenameVien/DataStructure