Study_farobi

단방향 연결 리스트와 순환 연결 리스트는 보통 헤드 포인터를 사용한다.

헤드 포인터는 연결리스트의 맨 처음 노드인 시작 노드를 가리킨다.

이중 연결 리스트는 양방향으로 연결되어 있는 리스트이므로 2가지 포인터를 사용한다.

다음 노드는 물론 이전 노드까지 접근 가능한 리스트이다.

이중 연결 리스트는 헤더 노드를 사용하는데 노드 자체를 사용하여 추가와 삭제를 용이하게 한다.

헤더 노드는 리스트의 첫번째 노드와 마지막 노드를 가리키는 포인터 값을 가진다.

왜 이중 연결 리스트는 헤더 노드를 사용해야 할까?

이중 연결 리스트는 pNode==pNode->pLLink->pRLink==pNode->pRLink->pLLink를 만족해야 한다.

만약 헤드 포인터를 사용하게 되면 pNode가 첫번째 노드일 경우에 pNode->pLLink는 노드가 아닌 단순한 헤드 포인터이므로(노드만 가리키는 포인터이므로) pNode->pLLink->pRLink가 성립될 수 없다. 노드의 추가와 삭제시에 고려해야 할 점이 늘어나므로 헤드 포인터가 아닌 헤더 노드로 구현하는 것

http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class04/class04_05.html

제자리 정렬 알고리즘 : 정렬 시 추가적인 메모리를 필요로 하지 않는 정렬 알고리즘을 말함

• 선택정렬/삽입정렬 - 제자리 정렬 알고리즘
• 퀵정렬/머지정렬 - 제자리 정렬 알고리즘 X

불안정/안정 정렬 알고리즘 : 같은 값일 경우 정렬 순서가 기존의 순서와 일치하지 않고 바뀌는 알고리즘

• 예를 들어 3, 2(1), 6, 8, 4, 2(2) 일 경우

불안정 정렬 알고리즘 : 2(2), 2(1), 3, 4, 6, 8

안정 정렬 알고리즘 : 2(1), 2(2), 3, 4, 6, 8

식으로 기존의 정렬 순서가 바뀌는 것을 불안정 정렬 알고리즘 이라고 함

• 정렬 순서를 정하는 값을 키(key) 라고 함

• 공간 복잡도(space complexity) : 프로그램을 실행시켜 완료하는데 필요한 메모리의 양(RAM관련)
• 고정 부분
• 프로그램의 입출력 특성과 관계 X - 횟수, 크기 등에 상관 X
• 보통 명령어 공간, 단순 변수, 일정 크기의 요소 변수, 상수들을 위한 공간을 포함
• 가변 부분
• 풀려고 하는 문제의 인스턴스에 의해 크기가 결정되는 변수가 필요로 하는 공간과, 참조된 변수가 필요로 하는 공간, 순환 스택 공간으로 구성
• 공간복잡도 S = C(상수) + Sp(인스턴스 특성)
• Sp는 함수가 얼마나 콜되는가에 따라 달라지는 것 같음
• 변수가 여러개 있다고 해서 Sp가 올라가는 것은 아님
• 순환의 깊이에 따라 Sp가 올라갈 수도 내려갈 수도 있음

• 시간 복잡도(time complexity) : 프로그램을 실행시켜 완료하는데 필요한 컴퓨터 시간(CPU관련)
• 프로그램에 소요되는 시간은 컴파일 시간 + 실행 시간 - SUM(명령어들의 수행시간 * 명령어들이 몇번이나 실행됐는지 센 결과)
• 컴파일 시간은 인스턴스 특성과는 무관하며 컴파일된 프로그램을 재컴파일 하지 않고 여러번 수행된다는 가정 하에 무시 가능 - 프로그램 실행 시간만 고려해도 OK
• 각 단계수(실행 횟수)를 고려하여 시간 복잡도를 계산
• 주석 : 단계수 0
• 선언문 : 변수/상수 정의문, class, struct, union, template, 접근자, 함수 타입 결정문 등은 단계수 0
• 비실행문이거나, 관련 함수가 기동되는 비용에 포함되므로
• 산술식 및 지정문
• 산술식 : +, -, *, / 등은 단계수 1, 다만 함수 호출을 포함하는 산술식은 예외
• 지정문 : = 등은 단계수 1, 다만 인스턴스 특성의 함수를 대입하는 경우 인스턴스 특성과 같은 단계수를 가짐
• 반복문 : 제어 부분만 단계수 고려, 반복문이 실행되는 횟수
• 스위치 명령문 : 수행되는 식의 단계수와 동일, 각 조건의 비용은 자신의 비용 + 앞서 나온 모든 조건의 비용
• if-else문 : 각 수행문에 따라 단계수 할당
• 함수 호출
• 매개변수가 인스턴스 특성에 의존하는 값이 아니라면 단계수 1, 의존하는 값이라면 값 인자의 크기가 단계수, 순환적이라면 지역변수도 고려
• 메모리 관리 명령문 : new, delete, sizeof 등 단계수 1
• new와 delete의 경우 생성자와 소멸자를 묵시적으로 호출할 수 있는데 이때는 함수 호출과 같은 방법으로 계산됨
• 함수 명령문 : 단계수 0
• 분기 명령문 : continue, break, goto, return 등 단계수 1, return 반환값; 일 경우 반환값이 인스턴스 특성의 함수라면 단계수는 반환값과 같음

밑의 예제를 통해 시간 복잡도를 조금 쉽게 이해하며 계산해보기

각 라인당 몇번 실행되는지 구한 후 다 더하면 OK

내가 변화시키고 싶은 특성들을 정해두고 그 특성에 맞춰 시간 복잡도를 계산하는 것이 좋음

• 균형 분기점(break even point) : 시간 복잡도가 큰 A와 작은 B가 있을 때 A가 B보다 빠를 수 있는 조건이 되는 n이 존재함. 그 때의 n이 균형 분기점
• 점근 표기법
• Ο(빅오) : 알고리즘 실행 시간의 상한을 나타냄 - 최악의 경우
• Ω(오메가) : 알고리즘 실행 시간의 하한을 나타냄 - 최고의 경우
• Θ(세타) : 알고리즘 실행 시간의 평균을 나타냄 - 평균의 경우