[알고리즘] 복잡도,빅오 표기법 O, 자료구조(리스트, 연결리스트)

220928 작성

<본 블로그는 "가장 쉬운 독학_알고리즘 첫걸음편 python 편"의 서적를 참고해서 공부하며 작성하였습니다>

 

 

 

1️⃣ 복잡도

: 말 그래로 계산의 복잡도

• 시간 복잡도 : 처리에 얼마나 많은 시간이 걸리는지
• 공간 복잡도 : 메모리 등의 기억 용량을 얼마나 필요로 하는지

 

2️⃣ 복잡도 작성법

: 전체 복잡도에 큰 영향을 기치지 않는 부분을 무시하고 복잡도를 작성

• 빅오 표기법 O
• 입력 크기 n의 변화에 따라 시간 복잡도가 달라짐

처리 시간	시간 복잡도	예
짧다 ↑ . . . . . ↓ 길다	O(1)	리스트 접근
	O(logn)	이진 검색
	O(n)	선형 검색
	O(nlogn)	병합 정렬
	O(n^2)	선택 정렬, 삽입 정렬
	O(n^3)	행렬 문제
	O(2^n)	배낭 문제
	O(n!)	외판원 문제

 

3️⃣ 최악 시간 복잡도 & 평균 시간 복잡도

🤍 최악 시간 복잡도

: 가장 시간이 오래 걸리는 데이터의 복잡도

 

🤍 평균 시간 복잡도

: 다양한 데이터를 고려하여 평균적으로 어느 정도의 복잡도가 될지를 판단하는 지표

 

 

4️⃣ 자료구조

🤍 연결 리스트

: 하나의 요소에 데이터를 저장할 뿐만 아니라, 다음 요소의 주소(위치)를 갖는다

: 앞에서부터 순서대로 처리하거나, 데이터의 추가 삭제가 자주 발생할 경우에는 연결 리스트 선호

: (임의의 위치 데이터 직접 접근해 읽거나, 갱신이 많으면 리스트 선호)

https://hwan1402.tistory.com/75

• 연결 리스트 삽입
  • 기존 리스트
    • 삽입 위치 이후의 데이터를 하나씩 뒤로 움직이기
    • n개의 요소가 저장된 리스트에 새로운 요소를 삽입할 때는 최대 n개의 요솟값을 이동시켜야 함
    • 리스트의 삽입 복잡도는 O(n)
  • 연결 리스트
    • 삽입할 위치 앞의 요소가 가리키는 다음 요소의 주소를 A라 하면, 삽입할 요소의 다음 요소 주소로서 A 설정
    • 앞의 요소가 가리키는 다음 요소의 주소를 삽입한 요소의 주소로 변경
    • 요소가 많아져도 요솟값의 이동이 없으므로 일정 시간에 처리 가능
    • 연결 리스트의 삽입 복잡도는 O(1)
• 연결 리스트 삭제
  • 기존 리스트
    • 요소를 삭제하면 삭제한 위치가 비므로, 그보다 뒤에 있는 데이터를 하나씩 앞으로 움직이기
    • 리스트의 삭제 복잡도는 O(n)
  • 연결 리스트
    • 삭제하는 요소가 가지는 다음 요소의 주소를 이전 요소가 가지는 다음 요소의 주소로 설정ㅎ\
    • 요소를 이동할 필요가 없음
    • 연결 리스트의 삭제 복잡도는 O(1)
• 연결 리스트 읽기
  • 기존 리스트
    • 맨 앞부터 n번째 요소를 읽을 때 요소 번호를 지정해 읽는다
    • 인덱스를 지정한 읽기의 복잡도
    • 리스트의 읽기 복잡도는 O(1)
  • 연결 리스트
    • n번째 요소를 읽으려면 맨 앞부터 순서대로 n까지 세면서 읽기
    • 인덱스를 지정해 읽음. 데이터의 수가 늘어날수록 처리 시간 증가
    • 연결 리스트의 읽기 복잡도는 O(n)

 

---

https://velog.io/@averycode/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D%ED%81%90%EA%B7%B8%EB%9E%98%ED%94%84-feat.Python 를 참고해서 적었습니다. : )

🤍 큐

: 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장

• add(item): item을 리스트의 끝부분에 추가
• remove(): 리스트의 첫 번째 항목을 제거
• peek() : 큐의 가장 위에 있는 항목 return
• isEmpty(): 큐가 비어있을때, true를 return

 

 

🤍 스택

: 한쪽 끝에서만 자료를 넣고 뺄 수 있는 선형구조(LIFO : LAST IN FIRST OUT)로 된 자료구조

• pop() : 스택의 가장 위(peek)에 있는 항목 제거
• push(data) : data 하나를 스택의 가장 위(peek)에 추가
• peek() : 스택의 가장 위에 있는 항목 return
• isEmpty(): 스택이 비어있을때, true를 return

 

🤍 그래프

: 노드(N, node)와 그 노드들을 연결하는 엣지(E, edge)를 포함하는 비선형 자료구조

: 연결되어있는 객체 관의 관계를 표현

• 무방향 그래프(Undirected Graph)
  • 간선을 통해서 양방향으로 갈 수 있다.
  • (A,B) = (B,A)
• 방향그래프 (Directed Graph)
  • 간선에 방향성이 존재하여 해당 방향으로만 유효
  • A -> B 는 <A,B>로 표기
  • <A,B> != <B,A>
• 가중치 그래프 (Wighted Graph)
  • 간선에 비용/가중치가 할당된 그래프