[ 자료구조 ] O 표기법, 큐, 스택

[ 자료구조 ] O 표기법, 큐, 스택

 

<프로그램 개발 단계>

 

1. 요구사항 분석(Requirement Analysis)

프로그램 개발 사용자, 기능, 성능, 기능, 요구사항

2. 설계 (Design)

플로우 차트 등 설계 도구 사용

3. 프로그래밍 (Programming)

플로우 차트를 프로그램 언어로 바꾼다.

4. 테스트 (Testing)

사용자에 세 샘플 데이터를 받아 실험한다.

5. 사용 (Use)

전달받아 사용, 설치, 수행, 해결방법 전달

6. 사용 및 보수 단계 (Maintenance)

 

 

<좋은 프로그램이란?>

프로그램 기능 수행이 정확해야 한다.

 

<세 수의 정렬>

MAX , MIN, MID 선언하고 두 개씩 비교

 

<알고리즘>

left	middle	right
0	5	10
6	8	10
6	6 (6.5) 실수 버림	7
7	7	7

알고리즘 : 어떤 일을 하는 절차

정의 : 명령의 집합

 

<알고리즘이 갖출 조건>

입력이 있다

출력이 있다

명확해야 한다

유한성

 

<알고리즘의 서술>

순서, 연속 : 명령어 다음에 다음 명령어

반복 : 명령어가 반복이 된다.

조건 : 조건에 따라 명령의 수행이 결정됨

 

<선택 정렬>

n개의 데이터 (n-1) 과정 반복.

가장 작은 수를 선택하여 바꾼다.

바꾸는 과정은 (n-1)(n-1) 번 반복된다.

 

선형 검색 : n개의 데이터를 하나씩 검색

이진 검색 : 크면 (오-1) / 작으면 (왼+1) / 같으면 반환

 

정렬된 데이터의 중간에 있는 데이터를 비교

찾는 데이터가 앞에 있는지 뒤에 있는지

찾아야 하는 데이터가 (1/2)로 줄어듦

 

이진 검색 4번 하면 16 데이터 검색 가능

이진 검색 5번 하면 32 데이터 검색 가능

이진 검색 10번 하면 1024 데이터 검색 가능

 

인덱스의 설정값

left=0, right=n-1, middle = (left+right)/2

 

해당되는 경우 왼/오를 잘라먹어

1) searchnum < list [middle]더 크면 오-1

right를 middle로 설정(right = middle-1)

2) searchnum > list [middle] 작으면 왼+1

left를 middle+1로 설정(left = middle+1)

3) searchnum = list [middle] 같으면 반환

middle을 반환(return middle)

 

일반적으로 데이터 11개면 4번 수행된다.

left> right.

 

 

 

728x90

 

 

<공간 복잡도> 메모리 영역

 

필요 공간이 데이터의 개수에 따라 변함

list [], n, tempsum, i => n+3개 데이터 공간

float sum(float list [], int n)

{ float tempsum = 0;

int i;

for(i = 0; i < n; i++)

tempsum += list [i];

return tempsum;

}

 

<시간 복잡도>

명령어 실행 횟수

절대적인 시간 X 연산의 개수 T(p) O

어느 정도 일을 하나요?? 연산 횟수

 

<O 표기법>

상한 함수

O(g(n)) : f(n)의 수행 복잡도

f(n) = O(g(n))

 

최악의 경우에 관심을 갖는다.

최악의 경우는 상한 함수가 관심 대상이다.

 

<O 표기법 순서>

O(1)

O(logn)

O(n^(1/2))

O(n)

O(nlogn)

O(n^2)

O(n^2 logn)

O(n^3)

O(2^n) (X) 컴퓨터로 해결 불가능

O(n!) (X) 컴퓨터로 해결 불가능

 

단일 반복문 = O(n)

이중 반복문, i++ = O(n^2)

 

단일 반복문, i = i*2 O(logn)

i = 2^n + 1에 비례한다.

함수를 n에 대해서 바꾸면 밑이 2인 logn

이건 logn과 같다.

 

<배열>

0~1000을 더하면 4095이다.

배열, 구조체 => 포인터를 이용해 주소 전달

array : 원소 같아야 함

 

<구조체>

struct : 원소가 달라도 돼.

필드들을 합해 데이터를 구성함

구조체는 각 데이터 타입과 이름 있음

 

<스택>

push(), pop(), top(맨 앞, 맨 앞, 비어있을 때-1)

Last In First Out (LIFO)

insert Last, delete First

 

<push>

stack [++top] = item;

// top = top + 1;

// stack [top] = item;

 

<pop>

return stack [top--];

// i = stack [top];

// top = top –1;

// return i;