Python2 07일차 수업 정리_알고리즘의 효율성과 시간 복잡도, 표기법(오메가, 세타, 빅오), 공간 복잡도, 연결리스트(Linked List)

- 알고리즘의 효율성 과 시간 복잡도

- 표기법(오메가, 세타, 빅오)

- 공간 복잡도 

- 연결리스트(Linked List)

 

 

---

- 알고리즘의 효율성, 시간 복잡도

 

알고리즘의 효율성이란 계산 속도와 메모리 사용량으로 평가하는 것을 말한다.

이는 사용하는 자료구조에 따라 큰 영향을 받는다. 

 

시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다.

같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 것이 좋은 코드이며, 
효율적인 알고리즘 구성을 위해 시간 복잡도 측면을 고려하며 중요하게 본다.

 

---

- 표기법(오메가, 세타, 빅오)

점근적 표기법으로 

오메가 표기법 최상의 경우	ex) 정류장에 도착하자마자 버스가 온다를 가정하고 가장 빨리 목적지에 도착할 수 있지만 항상 이 상황을 기대할 수 없다. (정확도가 낮다)
세타 표기법 평균의 경우	ex) 평균적인 시간에 버스가 도착한다를 가정 1년 동안 버스를 기다린 시간의 평균을 평균적인 경우로 볼 수 있다.
빅오 표기법 최악의 경우	ex) 이전 버스가 출발하자마자 정류장에 도착한다 가장 많이 기다려야 하지만 반대로 이 상황을 고려해서 집에서 출발하면 절대 지각하지 않는다.

 

빅오 표기법(Big-O)이란

데이터의 양(숫자)이 커질수록 차수가 가장 큰 항의 영향이 절대적.

알고리즘이 복잡할수록 평균 복잡도를 구하기 어려워 최악의 경우로 알고리즘의 성능을 파악하는 것.

복잡도	소요시간	의미	예시
O(1)	상수시간	문제를 해결하는데 오직 한 단계만 처리	스택 push, pop
O(log n)	로그시간	문제를 해결하는데 필요한 단계들이 특정 요인에 의해 줄어듦	이진트리
O(n)	직선적 시간	문제를 해결하기 위한 단계의 수와 입력값이 1 : 1 관계를 가짐	for문
O(n logn)	선형로그시간	문제를 해결하기 위한 단계의 수가  n*(log2n)번 만큼의 수행시간을 가진다	퀵 정렬, 병합정렬, 힙정렬
O(n^2)	2차시간	문제를 해결하기 위한 단계의 수는 입력값 n의 제곱	이중 for문, 삽입정렬, 버블정렬

 

---

- 공간 복잡도 

공간 복잡도란 (메모리를 얼마나 차지할지)

프로그램 실행과 완료에 얼마나 많은 공간(메모리)이 필요한지 타나낸다.

알고리즘을 실행시키기 위하여 필요한 공간(space)를 2가지로 나눌 수 있다. 

 

1. 알고리즘과 무관한 공간, 즉 고정 공간
- 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등

2. 알고리즘과 밀접한 공간, 즉 가변 공간
- 문제를 해결하기 위해 알고리즘이 필요로 하는 공간, 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택 등

 

---

- 연결리스트(Linked List)

 

연결리스트(Linked List)란 링크를 이용해서 리스트를 만드는 것. 

: 노드(Node)들이 서로 연결된 형태로 구성된 선형 자료구조
* 노드(Node) :  데이터(값)  +  다음노드의 주소

 

노드는 요소를 저장하는 data 필드와 다음 노드를 가르키는 next필드로 구성

data 필드 : 정수, 실수, ... next 필드 : 다음 노드를 가르키는 링크(자바에서는 레퍼런스, C언어 포인터)

 

연결리스트 종류

1) 싱글(단일) 연결리스트 2) 더블(이중) 연결리스트 3) 원형 연결리스트

 

연결리스트의 구성 
연결리스트의 접근은 첫번째 노드부터 시작
-> 첫번째 노드를 밟은 다음 링크(next)를 타고 그 다음 노드들에 차례대로 접근
-> 연결리스트의 객체는 리스트의 노드들을 직접 저장할 필요가 없고 

리스트의 첫번째 노드에 접근할 수 있는 레퍼런스만 갖고 있으면 됨

head [데이터][주소값] -> [데이터][주소값] -> [데이터][주소값]

 

노드 생성, 삽입, 삭제
: 데이터와 링크로 구성된 항목인 노드를 만들어서 생성할 수 있음

 

리스트
: 데이터를 일렬로 늘여놓은 형태인 선형 자료구조
  순서가 있음(인덱스 번호를 가짐)

파이썬 내장 리스트의 한계
: 리스트는 동적배열로 구현 (동적배열 => 늘였다 줄였다 가능)
배열을 사용할 경우 공간을 미리 확보해야함. 

리스트에 요소가 얼마나 들어올지 예상하기 어려워 많든 적든 공간 낭비가 심함.(java이야기?)

 

단일 연결리스트 예제 참고 

# 쓰앵님 답
# <실습> 노드 생성
# Node 클래스 생성
# n1, n2, n3, n4 객체 생성
# data에는 1, 2, 3, 4
# 연결 : n1 -> n2 -> n3 -> n4

class Node :
    # 생성자
    def __init__(self, data, link = None) :
        self.data = data
        self.link = link

# 객체 생성
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)

# 데이터 확인
# print(n1.data)
# print(n2.data)
# print(n3.data)
# print(n4.data)

# 연결
n1.link = n2
# print(n1.link == n2)
n2.link = n3
# print(n2.link == n3)
n3.link = n4
# print(n3.link == n4)
# print(n4.link)

# 출력
# 1 -> 2 -> 3 -> 4 -> None

# 반복문 사용
current = n1
print(current.data, end =" -> ")
while current.link != None :
    current = current.link
    print(current.data, end=" -> ")
print(current.link)

 

 

2024.02.20