빅오 표기법

조영규의 블로그

2014. 10. 29. 02:47 from Engineering

~~Edit~~

Introducing. Data Structure

Data structure(자료구조)란?

컴퓨터 프로그램의 특징은 2가지로 크게 구별됨.

컴퓨터에 의해서 실행되는 명령들의 집합이란 점.
명령을 수행하기 위해 내부적으로 여러 자료를 저장한다는 점.

즉 프로그램이란 자료(데이터) 집합과 명령(알고리즘) 집합의 집합

효율적 자료구조라는 것.

실행 시간 (Time complexity) 최소화.
저장 공간 (Space complexity) 절약.

여기서 저장 공간의 절약이란 프로그램 실행에 필요한 메모리가 적다는 의미.
실행 시간이란 특정 기능을 하는데 걸리는 시간을 의미.

알고리즘이란?

컴퓨터 명령 자체의 효율성을 증가시키기 위한 절차나 방법.
효율적 알고리즘을 위해서는 좋은 자료구조가 선행되어 바탕이되어야.

자료의 종류. (형태에 따라)

단순 구조. (Primitive Data Structure & Base Data Structure)
정수, 문자열, 실수 등
선형 구조. (Linear Data Structure)
리스트, 스택, 큐, 덱
각각의 자료구조가 선형적으로 연결되있는 것.
앞자료와 뒷자료가 1:1 관계.
비 선형 구조. (Non-linear Data Structure)
계층 구조(Hierarchical Structure) 혹은 망 구조(Network Structure)을 가지는 경우.
트리와 그래프가 포함. 앞뒤자료의 선후관계가 1:1이 아님.
파일 구조. (File Organization)
보조 기억장치에 저장되는 파일에 대한 자료구조.
메모리에 한번에 올릴(Loading) 수 없는 대용량의 자료를 대상으로 함.
순차적 파일 구조(Sequential), 상대적 파일 구조(Relative), 색인 파일 구조(Indexed Sequential) 및 다중키 파일 구조(Multi - key)등이 있다.

추상 자료형. (Abstract Data Type.)

정보은닉(Information Hiding)을 위해 사용. 중요한 정보만 나타내고 중요하지 않은 정보는 숨기는 방법.

자료와 자료형

자료와 자료형은 다르다! 뭔가 별거아닌데 충격적.

자료 + 연산 = 자료형
data + operation = data type
예) 정수 자료형 = 자료 (1,2,3,-1,-2등등) + 연산 (더하기, 빼기, 곱하기, 나누기, 나머지연산)

추상자료형

추상적으로 정의된 자료형. 미술에서 추상화는 사물을 사실적으로 그리지 않고 사물의 본질 혹은 두드러진 특성을 관념적으로 그리는 것 의미. 이와 유사하게 세부적이고 복잡한 것을 생략하고 중요한 것만 나타낸는 것.

예) 추상 자료형 콕 찌름 메세지(페이스북 콕 찌르기).

자료 3개.
콕 찌른 시간.
보내는 이.
받는 이.
명령 :

이름	입력	출력	설명
변경()	찌름 메세지 p, 변경 보내는 이 s, 변경 받는 이 r, 변경 시간 t	T/F	보내는 이와 받는 이 변경. 존재하지 않는 회원일 경우 실패
비교()	찌름 메세지 p	T/F	두 메세지가 같은지 비교.

알고리즘

문제를 해결하기위한 절차.
5가지 특성을 필수로 가지게 됨.

입력(Input) : 입력되는 자료가 0개 이상.
출력(Output) : 1개 이상의 출력값 가져야.
명백성(Definitenness) : 각 명령어는 모호하지 않아야.
유한성(Finiteness) : 한정된 수 단계이후 종료되어야.
유효성(Effectiveness) : 모든 명령은 실행 가능해야.

알고리즘의 표현 방법.

자연어(Natural Language) : 사람이 사용하는 일반적 언어.
순서도(Flow Chart) : 알고리즘의 도식화
의사 코드(Psudo Code) : 가상의 프로그램 언어로 표현
프로그래밍 언어

알고리즘의 분석 기준

== 시간 복잡도와 공간 복잡도
현대의 컴퓨터 과학에서는 시간 복잡도를 공간 복잡도보다 대부분 우선시.

시간 복잡도 : 알고리즘 실행에 걸리는 시간.
실제 시간 측정 or 실행되는 명령문의 개수를 계산.
실제 시간 측정의 경우 간단하게 측정 가능하지만 컴퓨터 성능에 종속적. -객관성 낮음
그래서 실행되는 명령문 개수를 기준으로 판단 -->> N에관한 관계식으로 표현.

사실 일반적으로 시간 복잡도는 == O(빅 오;Big-Oh notation)다.

연습문제

(in 열혈강의 자료구조 - 프리렉)

선형 구조에 속하는 자료구조와 비 선형 구조에 속하는 자료구조를 각각 적어보세요.
선형 구조 : 리스트, 스택, 큐, 덱
비 선형 구조 : 트리 (Hierartchical Structure), 그래프 (Network Structure)
다음과 같은 연산자를 포함하는 MP3 플레이어의 추상 자료형을 설계해 보세요.
```
 Play, Stop, Pause, Add_MP3, Delete_MP3, Get_MP3_Count
```
자료 : 곡 목록, 불리언 형 플래그(재생중인지), 현재 재생 중 곡 번호, 재생 시간
연산 :
play(mp3) : 0번부터 재생.
stop(mp3) : 멈춤.
pause(mp3) : 현재 재생중 곡번호, 재생시간에 데이터 넣고 플래그 off로.
Add_MP3(mp3) : 곡 목록 추가
Delete_MP3(mp3) : 현재곡 삭제
Get_MP3_Count(mp3) : 곡 목록 사이즈 반환.
알고리즘의 정의는 무엇인가요? 그리고 알고리즘이 만족시켜야 할 5가지 특징은 무엇인가요?
문제를 해결해 나가는 절차.
입력, 출력, 명백성(Definiteness), 유한성(Finiteness), 유효성(Effectiveness)
다음과 같은 소스가 있다고 할 때, 다음 질문에 답해보세요.
(1) n에 대한 시간 복잡도 함수를 구해보세요. 단, 덧셈, 곱셈, 나눗셈등 연산 횟수를 정확히 고려해야 합니다.
```
 2n *  3n + n + 1
```
= 6n^2 + n + 1
(2) 빅-오 표기법으로 시간 복잡도를 나타내 보세요.
```
 for(;i<n;i<-i+1){
     for(j<-0;j<n;j<-j+1){
         sum <- sum + j;
     }
 }
```
= O(n^2)
다음 시간 복잡도 함수들을 빅-오 표기법으로 나타내 보세요.
```
 6n^3 + n! + 5n + 4 O
```
= n!
```
 4nlogn + 5n^2 + 2 O
```
= n^2
```
 2^n + n^3 + 5 O
```
= 2^n
다음을 실행 시간이 적게 걸리는 순으로 나열하세요.
```
 O(n)  O(n^2)  O(n^3)  O(n!)  O(logn)  O(2^n)  O(nlogn)
```
= O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n) O(n!)

스터디에서 토론한 것.

데이터구조는 알고리즘의 일부다. 그리고 알고리즘은 데이터 구조의 일부다. 서로가 서로에게 영향을 미치는 관계라고 생각한다.
알고리즘을 통해 데이터구조를 구현. 따라서 상호 보완적. 결국 서로는 서로와 동등한 지위를 갖는다 생각.
프로그램 랭귀지로 알고리즘 구현시 명백성을 자동으로 포함시킬 수 있다. 당연히 컴퓨터에 시켜야 하니까.
무한 동작한 행위는 알고리즘이라고 하지 않는다. 이게 좀 특이한 듯.
형식이 있다고들 하는데 psudo code는 형식이 필요없다고 생각한다. 사람마다 다를 수 있지만 서로 알아볼 수 있으면 된 것 아닌가?
자연어는 설명을 쭉 쓰는 건데 한 눈에 보기 힘들기에 별로 좋지 않을 수 있지만 전체적 흐름과 그 함수의 특성을 러프히 설명할 때 유용할 듯.
- 그런데 그렇게 되면 알고리즘이 아니잖아. 명백성이 없어지니까.
프로그래밍언어는 알고리즘 표현에서 당연한 것.
- 당연하지 않아. psudo code나 순서도로 표현하고 그걸 정리해서 구현 할 수도 있어. 반드시 코딩을 해야하는 건 아닌듯.

저작자표시 비영리 변경금지

'Engineering' 카테고리의 다른 글

Introducing. Stack. / 스택 자료구조 (0)	2014.11.07
Introducing. List. / 리스트 자료구조 (0)	2014.11.07
TF-IDF(Term Frequency - Inverse Document Frequency) / 단어 빈도와 역문서 빈도. (0)	2014.11.07
RSS 피드 표준의 구조 ( 채널, 아이탬등 ) (0)	2014.08.19
리눅스 디바이스 드라이버 Linux device driver / 읽기 read() / 쓰기 write() / 열기 open() / 닫기 close() - 1 (1)	2014.05.29
Core network와 Access network (0)	2014.03.18
인터넷이란 무엇인가?(구성,서비스), 프로토콜이란 무엇인가? (0)	2014.03.18
SIC/XE의 구조(Architecture), SIC과 어떻게 다른가?, Special symbols (0)	2014.03.06
SIC(Simplified Instructional Computer)의 구조(Architecture), 명령어 포멧(Instruction formats), 주소 형식(Addressing modes) (1)	2014.03.06
시스템 소프트웨어란?(응용 소프트웨어와 시스템 소프트웨어의 차이) (0)	2014.03.03

comments powered by Disqus

태그, 트랙백, 검색 상자 토글