[자료구조] 3. 시간복잡도 & 연결형 자료구조

1. 알고리즘의 성능 분석

 

알고리즘의 성능 분석

• 실행시간 측정법
  • 알고리즘의 실제 실행 시간 측정하는 것
  • 알고리즘을 실제로 구현해야한다
  • 동일한 HW/ SW 환경 사용해야 한다
• 알고리즘 복잡도 분석법
  • 직접 구현 x, 수행 시간 분석
  • 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
  • 연산의 횟수 = 입력 크기 n의 함수
    • 시간 복잡도 분석 : 수행 시간 분석
    • 공간 복잡도 분석 : 필요한 메모리 공간 분석
      • 주어진 문제를 해결하기 위한 대부분의 알고리즘이 비슷한 크기의 메모리 공간을 사용

 

실행시간 측정

• 실제 측정한 시간의 한계
  • 프로그래머의 숙련도
  • 구현에 사용된 언어의 종류
  • 알고리즘을 실행한 컴퓨터의 성능
  • 에 따라 수행 시간이 달라질 수 있다.

• 복잡도 분석
  • 구현하지 않고 알고리즘의 효율성 평가
    • 알고리즘의 연산 횟수를 대략적으로 계산
    • 복잡도 함수 T(n): 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력 크기 n에 대한 함수로 표현한 것
      • 기본적인 연산 : 더 작게 쪼갤 수 없는 최소 크기의 연산 (사칙연산, 대소 비교, 변수 할당, 출력 등)
• 복잡도 함수의 점근적 표기
  • 여러 항을 갖는 복잡도 함수를 최고차항만을 계수 없이 취해 단순하게 표현하는 방법
    • 빅오 (점근적 상한)
    • 빅오메가 (점근적 하한)
    • 빅세타 (점근적 동일)

 

빅오 표기법
(정의) 모든 n ≥ n0 에 대해서 f(n) ≤ cg(n) 이 성립하는 양의 상수 c와 n0가 존재한다면, f(n) = O(g(n))이다.

 

• 자주 사용되는 함수의 빅오 표기와 이름s
• 함수의 증가 속도
• 빅오 표기법의 문제점‘
• 빅오메가 표기법
• 빅세타 표기법
• 최선, 평균, 최악의 경우
• 순차탐색

 

 

선형 자료구조

(정적 배열 → 동적 배열 → linked 리스트→ 단뱡향 → 양방향 → circle )

정적 배열에서는 데이터 추가 삽입의 문제

동적 배열에서는 추가 삽입 문제는 해결했으나 삽입과 삭제 시 시간복잡도 문제

linked 리스트에서는 삽입 문제 해결.. 그러나 삭제 시 시간복잡도의 문제

양방향 linked 리스트.. 삭제할 때의 시간복잡도 문제 해결함

 

 

 

 

 

2. 리스트와 연결형 자료구조

 

• 리스트란?[차이 구분하기] 리스트, 선형 리스트 vs 집합집합은 순서의 개념이 없고 중복을 허용하지 않음 → 선형 자료구조 아님
• 리스트와 선형리스트는 순서를 가진 항목들의 모임.. 따라서 인덱스를 통한 접근이 가능하고 원소간 순서 구분 가능
• 가장 자유로운 선형 자료구조
• 리스트의 연산리스트의 상태를 변경시키며 인덱스를 통해 연산을 수행함..
  • 리스트의 시간복잡도
    • 추가임의의 위치에 데이터 추가 : O(n)
    • 말단에 데이터 추가 : O(1)
    • 삭제임의의 데이터 삭제 : O(n)
    • 말단 데이터 삭제 : O(1)
  리스트는 배열 구조… 로 구현함 → 정적 배열→ 근데 크기=용량의 상황에서 데이터 삽입 문제 해결?
  • 가변적인 크기
  • 배열의 크기가 부족할 경우, 두 배로 늘리는 형식으로 데이터 제어→ 기존 배열 해제
  • → 기존 배열의 데이터를 새 배열에 복사하고 항목을 삽입..
  Q. 꽉 찬 정적배열에서 말단에 데이터 추가할 때의 시간 복잡도는?배열의 크기를 증가시키고 기존 데이터를 복사해야 하므로 데이터 크기 n개에 영향 받음str = list() 와 같은 코드로 동적 empty 배열 생성append메서드를 통한 데이터 삽입 (말단)del - 임의의 데이터 삭제** 동적배열은 최전단에 데이터를 추가하고자 할 때 **O(n)**의 시간 복잡도를 가짐

  ---

• 즉, 리스트의 크기가 7000이라고 가정한다면 그만큼 오래 걸림..
• [-1]은 말단 데이터를 의미
• insert를 통한 데이터 삽입 (임의의 위치)
• 인덱스를 통한 접근
• 파이썬의 리스트는 “동적 배열”
• A. O(n)
• “동적 배열”
• 데이터의 위치를 알고있다고 가정한다면, 접근 시간복잡도는 O(1)
• 삽입, 삭제, 추가

 

 

 

3. 연결형 자료구조

• Linked List각 데이터가 다음 데이터를 가리키는 형태편의상 시작과 끝에 값 None인 노드를 배치한다linked 리스트에서 데이터 삽입 시간 복잡도는 O(1)
  • 삭제할 대상 이전 노드를 안다는 가정 하에는 O(1)
  • 모른다면 하나씩 탐색해야 하므로 O(n) → 탐색 시간복잡도
• 데이터 삭제 시간 복잡도는 ?
• 이전 노드의 next 연결을 자신으로 바꾸고 자신의 next 연결 설정
• 배열 구조에서 데이터 삽입 시간 복잡도는 O(n)
• 하나의 node는 자신의 data값과 다음 node를 가리킴 (다음 node의 값을 아는 것이 아님을 주의)
• 연결형 자료구조의 일종
• 양방향 Linked List각각의 데이터가 이전 및 다음 데이터를 가리키는 형식의 자료구조→ 삭제 대상 이전의 next를 자신 노드 next로→ 앞의 두 단계에서 링크 조정하였다면, 실질적 데이터 삭제
  • 단방향 linked 리스트와 달리, 삭제 대상 이전 노드의 정보를 바로 얻을 수 있음
  시간 복잡도 = O(n)
• → 자신 노드 next의 이전 노드를 자신 노드 prev로
• 데이터 삭제 방법
• linked 리스트 중 하나

 

 

 

4. 클래스와 객체지향

• 절차지향 vs 객체지향개체를 순차적으로 처리하여 프로그램 전체가 유기적으로 연결됨but… 차례대로 진행되다 보니 앞서 처리한 것에 문제가 생기면 하나하나 다 새로 만들어야 함… 낮은 효율성각 객체는 데이터를 가지고 있으며 특정한 절차 수행 가능서로 상호작용하는 다수의 객체로 구성된 프로그램 작성
• 객체 = 속성 + 기능
• → 객체지향언어 : 프로그램을 구성하는 중추적 개념 “객체”
• 컴퓨터 처리구조와 유사하여 실행 속도 빠름
• → 절차지향언어 : 주어진 문제를 해결하기 위해 일련의 절차를 따름
• python의 클래스(Class)각각의 객체에 대한 “설계도”인스턴스 : 클래스로부터 생성되는 각각의 개체(인스턴스 모두가 공유하는 속성… 클래스 내부,, 그러나 메서드 밖에 선언)(객체 생성하는 메서드에는 self… 즉 생성자가 필수임.. )
• 메소드 : 클래스 내에서 정의되고 사용되는 함수를 구분하여 일컫는 단어
• 속성 : 각각의 인스턴스가 가질 수 있는 데이터의 값
• 클래스 = 틀, 틀을 통해 객체 생성 = 인스턴스
• 객체지향 프로그램 구현을 위한 파이썬에서의 핵심 개념

 

 

 

 

5. 양방향 Linked List의 구현

• node 클래스 정의

class node:

	# 노드 객체 생성
	def __init__(self, data, prev, next):
		self.data = data
		self.prev = prev
		self.next = next
		
	# 데이터 삽입
	def insert(data, position):
		new_node = node(data, position, position.next
		new_node.prev.next = new_node
		new_node.next.prev = new_node
		return new_node
	
	# 데이터 삭제
	def delete(target):
		target.prev.next = target.next 
		target.next.prev = target.prev
	
	# 노드 순회
	def visit_all(start_node):
		now_node = start_node
		while True:
			print(now_node.data)
			now_node = now_node.next
			if now_node == None:
				break

head = node(None, None, None)
tail = node(None, None, None)

head.next = tail
tail.prev = head

			

 

 

 

 

 

 

 

 

 

 

 

 

 

참고

빅오 표기법 (big-O notation) 이란

 

[알고리즘] 시간복잡도, O(n) 빅오 표현법