본문 바로가기

전체 글115

(3)[Chapter11]알고리즘_성능분석_3_측정시간과 점근표기법 2024. 9. 1.
(2)[Chapter11]알고리즘_성능분석_2_퀵정렬_복습 각 정렬당, 비교연산 횟수, SWAP연산 횟수, 회전당 정렬 결과 분석퀵정렬부연설명 : 퀵정렬은 피벗에 위치에 따라 모든 연산횟수가 달라진다. 여기서 작성할 피벗은 첫,끝인덱스 기준 퀵정렬이다.# 데이터 크기가 N일 때, 정렬상태와 상관없이 비교연산,  SWAP연산 횟수가 일정하다.총 비교연산횟수 : (N-1)*N/2 ( But, 랜덤 피벗으로 할 때는, 최작의 정렬상태 총 SWAP연산 횟수 : N-1 (But, 랜덤 피벗으로 할 때는, 최작의 정렬상태 # 정렬 노트 분석 사진 :##퀵정렬 출력 장면 : 1) 끝 인덱스를 피벗으로 했을 경우 :1_1) 최악의 정렬 상태 :1_2) 최적의 정렬 상태 : 2) 랜덤 피벗으로 했을 경우 :2_1) 최악의 정렬 상태 :2_2) 최적의 정렬 상태 :##전체 코드 .. 2024. 8. 31.
(1)[Chapter11]알고리즘_성능분석_1_버블정렬,삽입정렬_복습 각 정렬당, 비교연산 횟수, SWAP연산 횟수, 회전당 정렬 결과 분석1_ 버블정렬1_1) 데이터 크기가 N일 때,총 비교 연산 횟수 : 1부터 N-1합 == (N-1)*(N)/2 (정렬상태와 상관없이)총 SWAP 연산 횟수 : 데이터 정렬 상태에 따라 다르다최악의 정렬 상태 : 오름차순 기준 정렬하려고 할 때, 정렬 전 배열이 내림차순으로 정렬되어있을 때, => SWAP연산 횟수 최대최적의 정렬 상태 : 오름차순 기준 정렬하려고 할 때, 정렬 전 배열이 오름차순으로 정렬되어있을 때, => SWAP연산 횟수 01회전 당 정렬 결과 (오름차순 정렬 기준) : 데이터 N개 중 최댓값이 맨 오른쪽에 배치 된다.1_2) 정렬 노트 분석 사진   ##버블정렬 출력 장면  2_ 삽입 정렬2_1) 데이터 크기가 N일.. 2024. 8. 31.
(18)[Chapter7]우선순위 큐와힙트리_이론+코드 #주요 핵심 이론(일반 힙트리와 우선 순위 힙트리의 차이들)  :1_ 규칙이 달라짐(삽입, 삭제연산)- 일반 힙 (최소힙 기준) : 삽입 : 부모노드 값 > 자식노드 값 => SWAP / 부모노드 값 종료삭제 : smllest : △내에서 ( Data필드) 값이 가장 작은 값 - 우선순위 힙(최소 Prior힙 값) :삽입 : 부모노드.Priority값 > 자식노드.Priority값 => SWAP / 부모노드.Priority값 종료삭제 : smllest : △내에서 ( Priority값) 값이 가장 작은 값 (※그래야 i자리에 가장 )2_ 구조체 구조일반 힙 : 전역 DATA 타입 선언, 힙트리 구조체우선순위 큐 : 노드 구조체(필드 : void*형 Data 변수, int형 우선순위 변수) , 힙트리 .. 2024. 8. 28.

티스토리툴바